Bus Routes

Posted: 19 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given an array of routes, such that routes[i] denote the bus station’s ith 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 routes[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 
routes[i][0] integers denote the bus station’s number of 
ith bus.
Output Format
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.
Constraints
1<=’T’<=10
1<=’n’<=400
1<=sum(length of routes[i])<=10^5
0<=routes[i][j],’source’,’target’<=10^6
Approach 1

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 ‘minBuses’ array with the default value infinity. Make minBuses[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 current1 station  is greater than minBuses[current]+1 then replace minBuses[current1] by minBuses[current]+1.
  • After bfs traversal if the minBuses[destination] is equal to infinity then return -1(since there is no path).Else return minBuses[destination].
Try Problem