I am trying to find all mother vertex in a directed graph.

A mother vertex in a directed graph G = (V,E) is a vertex v such that all other vertices in G can be reached by a path from v.

My Approach:

Do DFS on each vertex and check if all the vertex are reached on each start node. Time complexity : O(V*(V+E)).

I am looking for any better solutions with better complexity.

Any help would be appreciated.


1 Answer 1


Find the strongly connected components. If the component graph has more than one source, then there are no mother vertices. Otherwise, the mother vertices are those that belong to the single source.

  • $\begingroup$ Thanks. What do you mean by source in a component? If we take this graph,geeksforgeeks.org/wp-content/uploads/SCC.png It has 3 components,but has one mother vertex. $\endgroup$
    – starkk92
    Commented Dec 4, 2017 at 18:31
  • $\begingroup$ Actually 0,1,2 are all mother vertices. A source is a vertex with no incoming edges. $\endgroup$ Commented Dec 4, 2017 at 18:53
  • $\begingroup$ Is there a way where I can find source vertices by SCC? $\endgroup$
    – starkk92
    Commented Dec 4, 2017 at 23:08
  • 1
    $\begingroup$ I'll let you figure that out. $\endgroup$ Commented Dec 4, 2017 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.