Genos And Saitama

Moderate
0/80
profile
Contributed by
0 upvote
Asked in company
Microsoft

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4 4
0 1
0 3
1 2
2 3
1 3
6 3
5 3
0 1
3 4
0 3
Sample Output 1 :
2
-1
Explanation For Sample Output 1 :

In the first test case, there are two paths from 1 to 3. I.e. 1 -> 2 -> 3 or 1 -> 0 -> 3. So the distance from 1 to 3 is 2.


In the second test case, there is no path from 0 to 3. Hence the answer is -1.
Sample Input 2 :
2
2 1
0 1
1 0
5 4
0 1
1 2
2 3
3 4
0 4
Sample Output 2 :
1
4
Hint

 Iterate through the graph using BFS and increment the distance by 1 when moving from one level of nodes to another.

Approaches (1)
Breadth-first search

 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.
Time Complexity

O(V + E). Where V is the number of towns and E is the number of roads.

 

Since we are implementing Breadth-first search, which is a linear task,

Hence the time complexity is O(V + E).

Space Complexity

O(V), Where V is the number of towns in Saitama’s land.

 

We are using a queue to store all the nodes of a single level.

Hence the space complexity is O(V).

Code Solution
(100% EXP penalty)
Genos And Saitama
Full screen
Console