Найти все материнские вершины графа

Материнская вершина: Материнская вершина в графе G = (V, E) — это вершина v, такая, что все другие вершины в G могут быть достигнуты путем из v. Может быть ноль, одна или более одной материнской вершины в график. Нам нужно найти все материнские вершины в данном графе.

Пример :

Input : Given graph below
Output : 0 1 4 
Explanation : In the given graph, the mother vertices are 0, 1 and 4 as there exists a path to each vertex from these vertices.

Рекомендуется: сначала попробуйте свой подход на {IDE}, прежде чем переходить к решению.

Наивный подход:
Тривиальный подход будет состоять в том, чтобы выполнить DFS или BFS для всех вершин и выяснить, можем ли мы достичь всех вершин из этой вершины.

Временная сложность : O(V(E+V))

Эффективный подход:

• Найдите любую материнскую вершину v в заданном графе G, используя этот алгоритм.
• Если материнская вершина существует, то множество вершин графа G, образующих компоненту сильной связности и содержащих v , является множеством всех материнских вершин графа.

Как работает вышеупомянутая идея?
Если для графа существует материнская вершина, то все материнские вершины являются вершинами компонента сильной связности, которая содержит материнскую вершину, потому что, если v — материнская вершина и существует путь из u -> v , то u должна быть материнской также вершина.

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

Временная сложность: O(V+E)
Космическая сложность: O(V+E)