Mother Vertex

Problem Statement - link #

Given a Directed Graph, find a Mother Vertex in the Graph (if present). A Mother Vertex is a vertex through which we can reach all the other vertices of the Graph.

Your Task: You don’t need to read or print anything. Your task is to complete the function findMotherVertex() which takes V denoting the number of vertices and adjacency list as imput parameter and returns the verticex from through which we can traverse all other vertices of the graph. If there is more than one possible nodes then returns the node with minimum value.If not possible returns -1.

Expected Time Complexity: O(V + E)
Expected Auxiliary Space: O(V)

Examples #

Example 1:

Input:

Output: 0
Explanation: According to the given edges, all 
nodes can be reaced from nodes from 0, 1 and 2. 
But, since 0 is minimum among 0,1 and 3, so 0 
is the output.

Constraints #

• 1 ≤ V ≤ 500

Solutions #

class Solution
{
    public:
    void dfs(int v,vector<int> adj[],vector<int>&vis,stack<int>&st,bool check){
        vis[v]=1;
        for(int w: adj[v])
            if(!vis[w])
                dfs(w,adj,vis,st,check);
        if(check) st.push(v);
    }
    //Function to find a Mother Vertex in the Graph.
	int findMotherVertex(int V, vector<int>adj[])
	{
	    // Code here
	    vector<int> vis(V);
	    stack<int> st;
	    for(int i=0;i<V;i++)
	        if(!vis[i])
	            dfs(i,adj,vis,st,1);
	    int res=st.top();
	    fill(vis.begin(),vis.end(),0);
	    dfs(res,adj,vis,st,0);
	    int v = accumulate(vis.begin(),vis.end(),0);
	    if(v!=V) res = -1;
	    return res;
	}
};