Last Updated: 23 Aug, 2021
Genos And Saitama
Moderate
Asked in company
There are ‘N’ towns in Saitama’s land. Each town is connected to other towns(possibly none) using a road. Genos is in town ‘g’ and Saitama is in town ‘s’. Genos wants to meet Saitama as soon as possible. Help Genos reach Saitama with the minimum number of roads taken.
For Example:
g = 1 and s = 0
Now in this land, there is a path from 1 to 0 through town 4 which is the minimum path. Hence the answer is 2.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases. Then each test case follows:
The first line of each test case contains two integers, ‘V’ and ‘E’, denoting the number of towns and roads.
The next ‘E’ lines of the test case contain two space-separated integers, ‘a’ and ‘b’, denoting a road between ‘a’ and ‘b’.
The last line of the test case contains two space-separated integers, ‘g’ and ‘s’, denoting Genos’s and Saitama’s town.
Output Format :
For each test case, print the number of minimum roads taken to get from ‘g’ to ‘s’.
Output for each test case will 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 and return the answer.
If there is no way to reach Saitama, return -1.
Constraints :
1 <= T <= 10
1 <= V <= 1000
1 <= E <= (V * (V - 1)) / 2
0 <= g, s <= V-1
Time Limit: 1sec
Approaches
In this approach, iterate through the whole graph using BFS and whenever you encounter a new level of nodes, update the count by 1.
The steps are as follows :
- Initialize an integer “distance” in which we will store the level of nodes.
- Create a graph using the given nodes and a queue for storing the nodes to iterate through breadth-first search.
- Push ‘g’ to the queue and start Breadth-first search till the queue is not empty.
- Initialize an integer “sz” denoting the size of the current queue.
- Increment the value of “distance” by 1.
- Iterate through 0 to “sz” to iterate all the nodes of the current level.
- Pop the first node in the queue and check if the current node is the required node. If yes, then return “distance”.
- Push all the unvisited nodes connected to the current node into the queue.
- Continue this loop till all the nodes of the current level are not popped.
- After completing BFS, if the loop has not returned something yet, that means there is no path from ‘g’ to ‘s’, return -1.