Last Updated: 19 Mar, 2021
Bus Routes
Moderate
Asked in companies
This time Ninja is helping a lost passenger on a bus stop to reach his destiny with the minimum number of buses he needs to change, on the bus stop a chart is present which contains 'N' arrays. An array 'A' denotes the route that a bus will take, such that A[i] denotes the bus stop 'i'th bus will travel to.
For Example
If the bus route is [3, 6, 7], then it will travel in sequence
3 > 6 > 7 > 3 > 6 > 7….
You can travel between the bus stations through buses only. You are given the source bus station and destination bus station. You need to determine the minimum number of buses you need to reach the destination. If it is not possible to reach destination return -1.
Note:
Values of A[i] are distinct.
Input Format
The first line contains a single integer ‘T’ denoting the number of test cases.
The first line of the test case contains ‘N’, ‘SOURCE’, ‘TARGET’ denoting the number of buses, source station, and target station.
The next ‘N’ lines contain the stations that the bus will travel to.
The first integer of the ith line contains the total number of bus stations ith bus will travel to.
The next A[i][j] integers denote the bus station’s number of ith bus.
Output Format
For each test case, return the single integer denoting the minimum number of buses to take to travel from source to destination. If it is not possible to reach destination return -1.
Note:
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints
1 <= ‘T’ <= 10
1 <= ‘N’ <= 400
1 <= sum(length of A[i]) <= 10^5
0 <= A[i][j], ‘SOURCE’, ‘TARGET’ <=10^6
Time Limit: 1 sec
Approaches
The main idea is to do breadth-first search traversal from the source station. From the source station, we will traverse to the bus station which we can traverse using different buses.
Algorithm:-
- Create a ‘MIN_BUSES’ array with the default value infinity. Make MIN_BUSES[SOURCE]=0(Since we don’t need any bus to travel to the source station).
- Create an adjacency list such that BUSTATION[i] contains the list of buses that will visit the ith bus station.
- Start bfs traversal from the source bus station. Traverse all the buses that will visit the current bus station. If the bus is already visited move to next. Else mark the bus visited and traverse all stations corresponding to the bus. If the number of buses to visit the current station is greater than MIN_BUSES[current]+1 then replace MIN_BUSES[current1] by MIN_BUSES[current]+1.
- After bfs traversal if the MIN_BUSES[destination] is equal to infinity then return -1(since there is no path).Else return MIN_BUSES[destination].
Similar problems