How to find mother vertex in a directed graph in O(n+m)?

A mother vertex in a directed graph G = (V,E) is a vertex v such that all other vertices G can be reached by a directed path from v Give an O(n+m) algorithm to test whether graph G contains a mother vertex.

(c) from Skiena manual

Found only O(n(n+m)) way


ANSWERS:


When googling I actually found the answer here. If this is homework, you should think twice before peeking :)


Algorithm::

a) Do DFS/BFS of the graph and keep track of the last finished vertex 'x' .

b) If there exist any mother vertex, then 'x' is one of them. Check if 'x' is a mother vertex by doing DFS/BFS from vertex 'x'.

Time Complexity O(n+m) + O(n+m) = O(n+m)


I saw the solution. I dont think we need to find SCC. Just do a DFS from a random vertex and then do the DFS from the vertex with last finish time. If there is a mother vertex then it has to be this.


step1. Do topological sorting of vertices of directed graph.

step2. Now check whether we can reach all vertices from first vertex of topologically sorted vertices in step 1.

To perform a step 2, again initialize array discovered[i] to false and do dfs startin from first node of topologically sorted vertices.

If all vertices can be reached, then graph has mother vertex, and mother vertex will be the former of topologically sorted vertices.

time complexity: step1 takes O(n + m), step 2 takes O(n + m) so total O(n+m) + O(n+m) = O(n+m)



 MORE:


 ? How to find the minimum set of vertices in a Directed Graph such that all other vertices can be reached
 ? Guided Random Walk on graph to have a uniform distribution over all nodes as end-step
 ? how many graphs with 10 nodes and 2 edges
 ? Graph Theory - How to find nodes reachable from a given node within certain cost?
 ? Number of edge distinct paths in bipartite graph
 ? How to find probability of path in a directed graph?
 ? path between two disjoint sets (path algorithm)
 ? How to convert List of Edges to Adjacency Matrix in C++ with the number of edges connected to a vertex instead of ones?
 ? Reasonable type for Directed graph in Ocaml
 ? How to select k nodes in a fully connected graph with max separation between any pair of nodes?