Проверить, можем ли мы посетить все остальные узлы из любого узла в заданном направленном графе.

Опубликовано: 26 Февраля, 2023

Даны N узлов, каждый из которых пронумерован от 0 до N – 1, и ребер массива, где имеется направленное ребро из ребер [i][0] в ребра [i][1], задача состоит в том, чтобы найти, является ли мы можем путешествовать от любого узла ко всем другим узлам или нет.

Примеры:

Input: N = 2, edges[] = {{0, 1}, {1, 0}};
Output: True
Explanation: We can go to node 0 from 1 and node 1 from 0

Input: N = 3, edges[] = {{1, 0}};
Output: False

Подход с использованием алгоритма Косараджу:

An idea of solving this problem is to think in terms of finding strongly connected component (SCC) for directed graph, We know that a directed graph is strongly connected if there is a path between all pairs of vertices. 

So if there is only a single SCC then only we can visit all the nodes from any other node. The number of SCC can be found using Kosaraju’s algorithm.

Выполните следующие шаги, чтобы реализовать вышеуказанную идею:

  • Создайте список смежности adj1 для хранения графа.
  • Выполняйте DFS в случайном порядке вершин и сохраняйте посещенные вершины в стеке stk при откате.
  • Измените направление всех ребер графа adj1 и сохраните вновь созданный граф в adj2 .
  • Выполните dfs2 в порядке стека и подсчитайте сильно связанные компоненты в переменной scc .
  • Проверьте количество scc :
    • Если количество scc больше 1, вернуть false.
    • В противном случае вернуть true.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N+E), где E — количество ребер
Вспомогательное пространство: O(N+E)

РЕКОМЕНДУЕМЫЕ СТАТЬИ