1var numBusesToDestination = function(routes, source, target) {
2    if (source === target) return 0;
3
4    const stopToRoutes = new Map();
5
6    routes.forEach((route, i) => {
7        route.forEach(stop => {
8            if (!stopToRoutes.has(stop)) {
9                stopToRoutes.set(stop, new Set());
10            }
11            stopToRoutes.get(stop).add(i);
12        });
13    });
14
15    let queue = [[source, 0]];
16    const visitedStops = new Set([source]);
17    const visitedRoutes = new Set();
18
19    while (queue.length > 0) {
20        const [stop, buses] = queue.shift();
21
22        for (let route of stopToRoutes.get(stop) || []) {
23            if (visitedRoutes.has(route)) continue;
24            visitedRoutes.add(route);
25
26            for (let nextStop of routes[route]) {
27                if (nextStop === target) return buses + 1;
28
29                if (!visitedStops.has(nextStop)) {
30                    visitedStops.add(nextStop);
31                    queue.push([nextStop, buses + 1]);
32                }
33            }
34        }
35    }
36    return -1;
37};

1#include <vector>
2#include <unordered_map>
3#include <unordered_set>
4#include <queue>
5
using namespace std;

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if (source == target) return 0;

        unordered_map<int, vector<int>> stop_to_routes;
        for (int i = 0; i < routes.size(); ++i) {
            for (int stop : routes[i]) {
                stop_to_routes[stop].push_back(i);
            }
        }

        unordered_set<int> visited_source, visited_target;
        queue<pair<int, int>> q_source, q_target;

        q_source.push({source, 0});
        visited_source.insert(source);
        q_target.push({target, 0});
        visited_target.insert(target);

        while (!q_source.empty() && !q_target.empty()) {
            int res = -1;
            if (q_source.size() <= q_target.size()) {
                res = bfs(routes, stop_to_routes, visited_source, visited_target, q_source);
            } else {
                res = bfs(routes, stop_to_routes, visited_target, visited_source, q_target);
            }
            if (res != -1) return res;
        }

        return -1;
    }

private:
    int bfs(const vector<vector<int>>& routes, unordered_map<int, vector<int>>& stop_to_routes,
            unordered_set<int>& visited_this, unordered_set<int>& visited_other, queue<pair<int, int>>& q) {
        int count = q.size();
        while (count-- > 0) {
            auto [stop, buses] = q.front(); q.pop();
            for (int route : stop_to_routes[stop]) {
                for (int next_stop : routes[route]) {
                    if (visited_other.count(next_stop)) return buses + 1;
                    if (visited_this.insert(next_stop).second) {
                        q.push({next_stop, buses + 1});
                    }
                }
            }
        }
        return -1;
    }
};