Last Updated: 14 Jun, 2021
Doctor Ninja's House
Hard
Asked in companies
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.
Approaches
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.
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.