What is a Mother Vertex?
A mother vertex in a graph G = (V, E) is a vertex v such that all other vertices in G can be reached by a path from v
Example:
Input: Graph as shown above
Output: 5
Note: There can be more than one mother vertices in a graph. We need to output anyone of them.
For example, in the below graph, vertices 0, 1, and 2 are mother vertices.
Naive Approach: To solve the problem follow the below idea:
A trivial approach will be to perform a DFS/BFS on all the vertices and find whether we can reach all the vertices from that vertex.
Time Complexity: O(V * (E+V))
Auxiliary Space: O(1) It will be O(V) if the stack space for DFS is considered or if we use a BFS.
Find a Mother Vertex in a Graph
Write a function to find a mother vertex in the graph.