Problem Statement:

You are given an array routes representing bus routes where routes[i] is a bus route that the i^th bus repeats forever.

For example, if routes[0] = [1, 5, 7], this means that the 0^th bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... forever.

You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only.

Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible.

Example 1:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

Example 2:

Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output: -1

Constraints:

1 <= routes.length <= 500.
1 <= routes[i].length <= 10⁵
All the values of routes[i] are unique.
sum(routes[i].length) <= 10⁵
0 <= routes[i][j] < 10⁶
0 <= source, target < 10⁶

Solution:

Let us first start with a simpler problem and then extend our solution to the given problem statement.

Assume for a moment that the problem was a simple graph with adjacency list G and we wanted to find shortest distance between two nodes source and target. Then we would use the following logic:

 
int shortestDistanceBFS(vector<vector<int>>&G, int source, int target)
{
    queue<int> Q;
    Q.push(source);
    int ctr=0;
    vector<int> visited (n, false);
    while (!Q.empty())
    {
        for (int i=Q.size(); i>0; i--)
        {
            int cur = Q.front(); Q.pop();
            if (cur==target) return ctr;
            visited[cur] = true;
            for (int nbd: G[cur]) if (!visited[nbd]) Q.push(nbd);
        }
        ctr ++;
    }
    return -1;
}

Now, our problem statement has bus routes that denote reachability. So we first store the bus routes available from a node in reachable_routes. We also create a boolean array traversed_routes to store the routes that have been checked already as we proceed. Now we modify the following line:

 
for (int nbd: G[cur]) if (!visited[nbd]) Q.push(nbd);

We change this to work in our setting. For this we first find out all reachable routes from cur, check if the route has been traversed or not using traversed_routes and then if not traversed, we add all nodes of the route to our queue. The following snippet does all of this:

 
for (int route_id: reachable_routes[cur])
{
    if (!traversed_routes[route_id]) 
    {
        traversed_routes[route_id] = true;                        
        for (int nbd: routes[route_id]) if(!visited.count(nbd)) Q.push(nbd);
    }
}

Here is the complete solution:

 
class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) 
    {
        unordered_map<int,vector<int>> reachable_routes;
        for (int i=0; i<routes.size(); i++)
            for (int node: routes[i]) reachable_routes[node].push_back(i);
        queue<int> Q;
        Q.push(source);
        int ctr = 0;
        unordered_set<int> visited;
        vector<bool> traversed_routes(routes.size(), false);
        while(!Q.empty())
        {
            for (int i=Q.size(); i>0; i--)
            {
                int cur = Q.front();
                Q.pop();
                visited.insert(cur);
                if (cur==target) return ctr;
                for (int route_id: reachable_routes[cur])
                {
                    if (!traversed_routes[route_id]) 
                    {
                        traversed_routes[route_id] = true;                        
                        for (int nbd: routes[route_id]) if(!visited.count(nbd)) Q.push(nbd);
                    }
                }
            }
            ctr++;
        }
        return -1;
    }
};