Doctor Ninja's House
There are ‘N’ cities and ‘M’ paths connecting them. Doctor Ninja wants to purchase a house in a city ‘X’ such that she can reach any city from the city ‘X’.

Your task is to help Ninja to find her a house ‘X’, if you are given with ‘N’ cities and ‘M’ paths.

There can be more than one house ‘X’ possible. You need to output the house ‘X’ with minimum value. If you are unable to find any such house ‘X’, then return -1.

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: Consider the following Graph:

Vertices reachable from vertex 0: 0 - 1 - 3 - 2 - 4 - 5 - 7 - 6 Vertices reachable from vertex 1: 1 - 3 - 2 - 4 - 5 - 7 - 6 Vertices reachable from vertex 2: 2 - 1 - 3 - 4 - 5 - 7 - 6 Vertices reachable from vertex 3: 3 - 2 - 1 - 4 - 5 - 7 - 6 Vertices reachable from vertex 4: 4 - 5 - 7 - 6 Vertices reachable from vertex 5: 5 - 7 - 6 - 4 Vertices reachable from vertex 6: 6 - 4 - 5 - 7 Vertices reachable from vertex 7: 7 - 6 - 4 - 5 Clearly, there is only one vertex “ 0 ” in the graph, from which all other vertices are reachable. Hence, vertex “ 0 ” is the mother vertex of the above graph. There can be more than one mother vertices in a graph.

For Example, in the above graph, vertices 0, 1 and 2 are mother vertices.

Input Format:

The first line contains an Integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow. The first line of each test case contains two space separated integers ‘N’, denoting the number of cities (from 0 to ‘N-1’) and ‘M’, denoting the number of paths connecting cities. Next ‘M’ lines contain two space separated integers ‘u’ and ‘v’ denoting a path from a city ‘u’ to a city ‘v’, where { u, v } ∈ N.

Output Format:

For each test case, return an integer ‘X’, where ‘X’ is the minimum city which Doctor can buy. There can be more than one house ‘X’ possible. You need to output the house ‘X’ with minimum value. If you are unable to find any such house ‘X’, then return -1. The output of each test case should be printed in a separate line.

Note:

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints :

1

Question

Doctor Ninja's House

There are ‘N’ cities and ‘M’ paths connecting them. Doctor Ninja wants to purchase a house in a city ‘X’ such that she can reach any city from the city ‘X’.

Your task is to help Ninja to find her a house ‘X’, if you are given with ‘N’ cities and ‘M’ paths.

There can be more than one house ‘X’ possible. You need to output the house ‘X’ with minimum value. If you are unable to find any such house ‘X’, then return -1.

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:
Consider the following Graph:

Vertices reachable from vertex 0:
0 -> 1 -> 3 -> 2 -> 4 -> 5 -> 7 -> 6

Vertices reachable from vertex 1:
1 -> 3 -> 2 -> 4 -> 5 -> 7 -> 6

Vertices reachable from vertex 2:
2 -> 1 -> 3 -> 4 -> 5 -> 7 -> 6

Vertices reachable from vertex 3:
3 -> 2 -> 1 -> 4 -> 5 -> 7 -> 6

Vertices reachable from vertex 4:
4 -> 5 -> 7 -> 6

Vertices reachable from vertex 5:
5 -> 7 -> 6 -> 4

Vertices reachable from vertex 6:
6 -> 4 -> 5 -> 7

Vertices reachable from vertex 7:
7 -> 6 -> 4 -> 5

Clearly, there is only one vertex “ 0 ” in the graph, from which all other vertices are reachable. Hence, vertex “ 0 ” is the mother vertex of the above graph.

There can be more than one mother vertices in a graph.

For Example, in the above graph, vertices 0, 1 and 2 are mother vertices.

Input Format:

The first line contains an Integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains two space separated integers ‘N’, denoting the number of cities (from 0 to ‘N-1’) and ‘M’, denoting the number of paths connecting cities.

Next ‘M’ lines contain two space separated integers ‘u’ and ‘v’ denoting a path from a city ‘u’ to a city ‘v’, where { u, v } ∈ N.

Output Format:

For each test case, return an integer ‘X’, where ‘X’ is the minimum city which Doctor can buy. 
There can be more than one house ‘X’ possible. You need to output the house ‘X’ with minimum value. If you are unable to find any such house ‘X’, then return -1.
The output of each test case should be printed in a separate line.

Note:

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 10
1 <= N <= 10^4
1 <= M <= 10^5
0 <= X < N

Time Limit : 1 sec.

Accepted Answer

The task is to find a city 'X' from which all other cities can be reached in a given graph.

Find the mother vertices in the graph.
If there are multiple mother vertices, return the minimum value.
If there are no mother vertices, return -1.

Accepted Answer

Naive Approach

A trivial approach will be to perform a DFS on all the vertices and find whether we can reach all the vertices of the graph from that vertex or not.

Algorithm :

1. Implement the function 'addEdge', to store a path from vertex 'u' to vertex 'v'.

2. Implement the function 'dfs'.

1. Mark the current node as visited.

2. Recur for all the vertices adjacent to this vertex.

3. If the vertex is not visited yet, again implement the 'dfs' function for that vertex.

3. Implement the function 'findHouse'.

1. Initialize the 2-D vector 'adj' to store the adjacent vertices of a vertex.

2. Add a edge from node 'u' to node 'v' using function 'addEdge'.

3. Iterate through 0 to 'N-1' (say, iterator 'i').

1. Initialize all nodes as not visited.

2. Check for each vertex how many nodes are reachable.

3. Initialize 'flag' as zero.

4. Iterate through 0 to 'N-1' (say, iterator 'j').

1. If node is not visited, make 'flag' equal to 1 and break out of the loop.

5. If Mother vertex is found, return 1.

4. Return -1.

Space Complexity: O(n)Explanation:

O(‘N’), where ‘N’ is the number of vertices in a graph.

Space complexity will be O(N) due to the stack size, and in the worst case, the height of the stack can be N.

Time Complexity: OtherExplanation:

O(N(N + M)) where ‘N’ is the number of vertices and ‘M’ is the number of edges.

The time complexity for this approach is O(N(N + M)),which is very inefficient for large graphs, because we are applying DFS on all the vertices and again applying DFS.

Python (3.5)

'''
    Time Complexity: O(N(N + M)).
    Space Complexity: O(N).

    Where, N is the number of vertices. 
    and M Number of edges.
'''

def dfs(node, vis, adj):
    
    # Mark the current node as visited.
    vis[node] = True
    
    # Recur for all the vertices adjacent to this vertex.
    for itr in adj[node]:
        
        # If the vertex is not visited yet.
        if not vis[itr]:
            dfs(itr, vis, adj)
                        
def findHouse(paths, n, m):
    
    # To store the connections.
    adj = []
    
    for i in range(n):        
        adj.append([])
    
    for i in range(m):
        u = paths[i][0]
        v = paths[i][1]
        
        # Adding a edge from node 'u' to node 'v'.
        adj[u].append(v)
        
    # Initially all nodes are initialized as not visited.
    vis = [False for i in range(n)]
    
    for i in range(n):
        
        # Reset all values in vis as false.
        for k in range(n):
            vis[k] = False
            
        # Checking for each vertex how many nodes are reachable.
        dfs(i, vis, adj)
        
        # Initialize 'flag' as zero.
        flag = 0
        
        for j in range(n):
            
            # If node is not visited.
            if vis[j] == False:
                flag = 1
                break
                
        # Mother vertex found.
        if flag == 0:
            return i
        
    return -1

C++ (g++ 5.4)

/*

    Time Complexity: O(N(N + M)).

    Space Complexity: O(N).



    Where, 'N' is the number of vertices 

    and 'M' is the number of edges.

*/



void addEdge(int u, int v, vectoradj[]) {



    // There is a path from vertex 'u' to vertex 'v'.

    adj[u].push_back(v); 

}



void dfs(int node, vector &vis, vectoradj[]) {



    // Mark the current node as visited.

    vis[node] = true;

 

    // Recur for all the vertices adjacent to this vertex.

    for (auto itr = adj[node].begin(); itr != adj[node].end(); ++itr) {

        

        // If the vertex is not visited yet.

        if (not vis[*itr]) {

            dfs(*itr, vis, adj);

        }

    }

}



int findHouse(vector> paths, int n, int m) {



    // To store the adjacent vertices of a verex.

    vectoradj[n];



    for(int i = 0; i < m; i++) {



        int u = paths[i][0];

        int v = paths[i][1];



        // Adding a edge from node 'u' to node 'v'.

        addEdge(u, v, adj);

    }



    // Initially all nodes are initialized as not visited.

    vector  vis(n, false);



    for(int i = 0; i < n; i++) {



        // Reset all values in 'vis' as false.

        fill(vis.begin(), vis.end(), false);

        

        // Checking for each vertex how many nodes are reachable.

        dfs(i, vis, adj);



        // Initialize 'flag' as zero.

        int flag = 0;



        for (int j = 0; j < n; j++) {



            // If node is not visited.

            if (vis[j] == false) {

                flag = 1;

                break;

            }

        }



        // Mother vertex found.

        if(flag == 0) {

            return i;

        }

    }

    return -1;

}

Java (SE 1.8)

/*

    Time Complexity: O(N(N + M)).

    Space Complexity: O(N).



    Where, N is the number of vertices. 

    and M Number of edges.

*/





import java.util.ArrayList;



public class Solution {

    static void dfs(int node, ArrayList vis, ArrayList> adj){



        // Mark the current node as visited.

        vis.set(node, true);



        // Recur for all the vertices adjacent to this vertex.

        for (int itr : adj.get(node)){



            // If the vertex is not visited yet.

            if (!vis.get(itr)) {

                dfs(itr, vis, adj);

            }

        }

    }



    public static int findHouse(int[][] paths, int n, int m) {



        // To store the connections.

        ArrayList> adj = new ArrayList>();

        for (int i = 0; i < n; i++) {

            adj.add(new ArrayList());

        }



        for (int i = 0; i < m; i++) {

            int u = paths[i][0];

            int v = paths[i][1];



            // Adding a edge from node 'u' to node 'v'.

            adj.get(u).add(v);

        }



        ArrayList vis = new ArrayList<>(n);



        // Initially all nodes are initialized as not visited.

        for (int i = 0; i < n; i++) {

            vis.add(false);

        }



        for(int i = 0; i < n; i++) {



            // Reset all values in vis as false.

            for(int k=0;k                vis.set(k,false);

            }



            // Checking for each vertex how many nodes are reachable.

            dfs(i, vis, adj);



            // Initialize 'flag' as zero.

            int flag = 0;



            for (int j = 0; j < n; j++) {



                // If node is not visited.

                if (vis.get(j) == false) {

                    flag = 1;

                    break;

                }

            }



            // Mother vertex found.

            if(flag == 0) {

                return i;

            }

        }

        return -1;

    }



}

Accepted Answer

Optimized Approach

The idea is based on Kosaraju’s Strongly Connected Component Algorithm. In a graph of strongly connected components, mother vertices are always vertices of the source component in the component graph. If there exists a mother vertex (or vertices), then one of the mother vertices is the last finished vertex in DFS (or a mother vertex has the maximum finish time in DFS traversal). A vertex is said to be finished in DFS if a recursive call for its DFS is over, i.e., all descendants of the vertex have been visited.

Algorithm :

1. Implement DFS traversal on the given graph. While doing traversal keep track of the last finished vertex ‘lastFinished’. This step takes O(N+M) time.

2. If there exists a mother vertex (or vertices), the ‘lastFinished’ node must be one (or one of them). Check if ‘lastFinished’ node is a mother vertex by doing DFS from ‘lastFinished’ node. This step also takes O(N+M) time.

Space Complexity: O(n)Explanation:

O(‘N’), where ‘N’ is the number of vertices in a graph.

Space complexity will be O(N) due to the stack size, and in the worst case, the height of the stack can be N.

Time Complexity: OtherExplanation:

O(N + M) where ‘N’ is the number of vertices and ‘M’ is the number of edges.

Since we have traversed each vertex only once, therefore time complexity will be O(N + M).

Python (3.5)

'''
    Time Complexity: O(N + M).
    Space Complexity: O(N).

    Where, N is Number of vertices and M  
    is number of edges.
'''

def dfs(node, vis, adj):
    
    # Mark the current node as visited.
    vis[node] = True
    
    # Recur for all the vertices adjacent to this vertex.
    for itr in adj[node]:
        
        # If the vertex is not visited yet.
        if not vis[itr]:
            dfs(itr, vis, adj)
            
def findHouse(paths, n, m):

    # To store the connections.
    adj = []
    for i in range(n):
        
        adj.append([])
        
    for i in range(m):
        u = paths[i][0]
        v = paths[i][1]
        
        # Adding a edge from node 'u' to node 'v'.
        adj[u].append(v)
        
    vis = []
    
    # Initially all nodes are initialized as not visited.
    for i in range(n):
        vis.append(False)
        
    lastFinished = -1
    
    # Do a DFS traversal and find the last finished vertex.
    for i in range(n):
        
        # If the node is not visited yet.
        if vis[i] == False:
            
            dfs(i, vis, adj)
            lastFinished = i
    
    '''
            If there exist a mother vertex (or vetices) in given
            graph, then 'lastFinished' node must be one (or one of them).
    
            Now, to check if 'lastFinished' node is actually a mother 
            vertex (or graph has a mother vertex), we basically check 
            if every vertex is reachable from 'lastFinished' node or not.
    '''
    check = []
    for i in range(n):
        check.append(False)
        
    '''
            Do a DFS beginning from 'lastFinished' node to check if all 
            vertices are reachable from it or not.
    '''
    dfs(lastFinished, check, adj)
    
    for i in range(n):
        
        if check[i] == False:
            return -1
        
    return lastFinished

C++ (g++ 5.4)

/*

    Time Complexity: O(N + M).

    Space Complexity: O(N).



    Where, 'N' is the number of vertices. 

    and 'M' is the number of edges.

*/



void addEdge(int u, int v, vectoradj[]) {



    // There is a path from vertex 'u' to vertex 'v'.

    adj[u].push_back(v); 

}



void dfs(int node, vector &vis, vectoradj[]) {



    // Mark the current node as visited.

    vis[node] = true;

 

    // Recur for all the vertices adjacent to this vertex.

    for (auto itr = adj[node].begin(); itr != adj[node].end(); ++itr) {

        

        // If the vertex is not visited yet.

        if (not vis[*itr]) {

            dfs(*itr, vis, adj);

        }

    }

}



int findHouse(vector> paths, int n, int m) {



    // To store the adjacent vertices of a verex.

    vectoradj[n];



    for(int i = 0; i < m; i++) {



        int u = paths[i][0];

        int v = paths[i][1];



        // Adding a edge from node 'u' to node 'v'.

        addEdge(u, v, adj);

    }



    // Initially all nodes are initialized as not visited.

    vector  vis(n, false);

 

    // To store the last finished vertex (or mother vertex).

    int lastFinished = -1;

 

    // Do a DFS traversal and find the last finished vertex .

    for (int i = 0; i < n; i++) {



        // If the node is not visited yet.

        if (vis[i] == false) {



            dfs(i, vis, adj);

            lastFinished = i;

        }

    }

 

    /*

        If there exist a mother vertex (or vetices) in given

        graph, then 'lastFinished' node must be one (or one of them).

    

        Now, to check if 'lastFinished' node is actually a mother 

        vertex (or graph has a mother vertex), we basically check 

        if every vertex is reachable from 'lastFinished' node or not.

    */



    // Reset all values in vis[] as false

    fill(vis.begin(), vis.end(), false);

    

    /*

        Do a DFS beginning from 'lastFinished' node to check if all 

        vertices are reachable from it or not.

    */



    dfs(lastFinished, vis, adj);



    for (int i = 0; i < n; i++) {

        if (vis[i] == false) {

            return -1;

        }

    }

 

    return lastFinished;

}

Java (SE 1.8)

/*

    Time Complexity: O(N + M).

    Space Complexity: O(N).



    Where, N is Number of vertices and M  

    is number of edges.

*/



import java.util.ArrayList;



public class Solution {

    static void dfs(int node, ArrayList vis, ArrayList> adj){



        // Mark the current node as visited.

        vis.set(node, true);



        // Recur for all the vertices adjacent to this vertex.

        for (int itr : adj.get(node)){



            // If the vertex is not visited yet.

            if (!vis.get(itr)) {

                dfs(itr, vis, adj);

            }

        }

    }



    public static int findHouse(int[][] paths, int n, int m) {



        // To store the connections.

        ArrayList> adj = new ArrayList>();

        for (int i = 0; i < n; i++) {

            adj.add(new ArrayList());

        }



        for (int i = 0; i < m; i++) {

            int u = paths[i][0];

            int v = paths[i][1];

            

            // Adding a edge from node 'u' to node 'v'.

            adj.get(u).add(v);

        }



        ArrayList vis = new ArrayList<>(n);



        // Initially all nodes are initialized as not visited.

        for (int i = 0; i < n; i++) {

            vis.add(false);

        }



        int lastFinished = -1;



        // Do a DFS traversal and find the last finished vertex .

        for (int i = 0; i < n; i++) {



            // If the node is not visited yet.

            if (vis.get(i) == false) {



                dfs(i, vis, adj);

                lastFinished = i;

            }

        }



        /*

            If there exist a mother vertex (or vetices) in given

            graph, then 'lastFinished' node must be one (or one of them).

    

            Now, to check if 'lastFinished' node is actually a mother 

            vertex (or graph has a mother vertex), we basically check 

            if every vertex is reachable from 'lastFinished' node or not.

        */



        ArrayList check = new ArrayList<>(n);

        for (int i = 0; i < n; i++) {

            check.add(false);

        }



        /*

            Do a DFS beginning from 'lastFinished' node to check if all 

            vertices are reachable from it or not.

        */

        dfs(lastFinished, check, adj);



        for (int i = 0; i < n; i++) {

            if (check.get(i) == false) {

                return -1;

            }

        }



        return lastFinished;



    }



}

There are ‘N’ cities and ‘M’ paths connecting them. Doctor Ninja wants to purchase a house in a city ‘X’ such that she can reach any city from the city ‘X’.

Your task is to help Ninja to find her a house ‘X’, if you are given with ‘N’ cities and ‘M’ paths.

There can be more than one house ‘X’ possible. You need to output the house ‘X’ with minimum value. If you are unable to find any such house ‘X’, then return -1.

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.

For Example, in the above graph, vertices 0, 1 and 2 are mother vertices.

Input Format:

Output Format:

Note:

Constraints :

Top Wunderman Thompson Commerce Technical Associate interview questions & answers

Popular interview questions of Technical Associate