Bus Routes

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if (source == target) return 0;
        unordered_map<int, vector<int>> stopToRoutes;
        for (int i = 0; i < (int)routes.size(); ++i)
            for (int s : routes[i])
                stopToRoutes[s].push_back(i);
        unordered_set<int> visitedStops{source}, visitedRoutes;
        queue<int> q;
        q.push(source);
        int buses = 0;
        while (!q.empty()) {
            ++buses;
            for (int sz = q.size(); sz > 0; --sz) {
                int stop = q.front(); q.pop();
                for (int r : stopToRoutes[stop]) {
                    if (visitedRoutes.count(r)) continue;
                    visitedRoutes.insert(r);
                    for (int ns : routes[r]) {
                        if (ns == target) return buses;
                        if (!visitedStops.count(ns)) {
                            visitedStops.insert(ns);
                            q.push(ns);
                        }
                    }
                }
            }
        }
        return -1;
    }
};

func numBusesToDestination(routes [][]int, source int, target int) int {
    if source == target {
        return 0
    }
    stopToRoutes := map[int][]int{}
    for i, route := range routes {
        for _, s := range route {
            stopToRoutes[s] = append(stopToRoutes[s], i)
        }
    }
    visitedStops := map[int]bool{source: true}
    visitedRoutes := map[int]bool{}
    queue := []int{source}
    buses := 0
    for len(queue) > 0 {
        buses++
        sz := len(queue)
        for i := 0; i < sz; i++ {
            stop := queue[0]
            queue = queue[1:]
            for _, r := range stopToRoutes[stop] {
                if visitedRoutes[r] {
                    continue
                }
                visitedRoutes[r] = true
                for _, ns := range routes[r] {
                    if ns == target {
                        return buses
                    }
                    if !visitedStops[ns] {
                        visitedStops[ns] = true
                        queue = append(queue, ns)
                    }
                }
            }
        }
    }
    return -1
}

from collections import defaultdict, deque
from typing import List

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source == target:
            return 0
        stop_to_routes: defaultdict[int, List[int]] = defaultdict(list)
        for i, route in enumerate(routes):
            for s in route:
                stop_to_routes[s].append(i)
        visited_stops = {source}
        visited_routes: set[int] = set()
        q = deque([source])
        buses = 0
        while q:
            buses += 1
            for _ in range(len(q)):
                stop = q.popleft()
                for r in stop_to_routes[stop]:
                    if r in visited_routes:
                        continue
                    visited_routes.add(r)
                    for ns in routes[r]:
                        if ns == target:
                            return buses
                        if ns not in visited_stops:
                            visited_stops.add(ns)
                            q.append(ns)
        return -1

var numBusesToDestination = function(routes, source, target) {
    if (source === target) return 0;
    const stopToRoutes = new Map();
    for (let i = 0; i < routes.length; i++) {
        for (const s of routes[i]) {
            if (!stopToRoutes.has(s)) stopToRoutes.set(s, []);
            stopToRoutes.get(s).push(i);
        }
    }
    const visitedStops = new Set([source]);
    const visitedRoutes = new Set();
    let queue = [source];
    let buses = 0;
    while (queue.length > 0) {
        buses++;
        const next = [];
        for (const stop of queue) {
            for (const r of stopToRoutes.get(stop) || []) {
                if (visitedRoutes.has(r)) continue;
                visitedRoutes.add(r);
                for (const ns of routes[r]) {
                    if (ns === target) return buses;
                    if (!visitedStops.has(ns)) {
                        visitedStops.add(ns);
                        next.push(ns);
                    }
                }
            }
        }
        queue = next;
    }
    return -1;
};

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) return 0;
        Map<Integer, List<Integer>> stopToRoutes = new HashMap<>();
        for (int i = 0; i < routes.length; i++) {
            for (int s : routes[i]) {
                stopToRoutes.computeIfAbsent(s, k -> new ArrayList<>()).add(i);
            }
        }
        Set<Integer> visitedStops = new HashSet<>();
        Set<Integer> visitedRoutes = new HashSet<>();
        visitedStops.add(source);
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(source);
        int buses = 0;
        while (!q.isEmpty()) {
            buses++;
            for (int sz = q.size(); sz > 0; sz--) {
                int stop = q.poll();
                List<Integer> rs = stopToRoutes.get(stop);
                if (rs == null) continue;
                for (int r : rs) {
                    if (!visitedRoutes.add(r)) continue;
                    for (int ns : routes[r]) {
                        if (ns == target) return buses;
                        if (visitedStops.add(ns)) {
                            q.offer(ns);
                        }
                    }
                }
            }
        }
        return -1;
    }
}

function numBusesToDestination(routes: number[][], source: number, target: number): number {
    if (source === target) return 0;
    const stopToRoutes = new Map<number, number[]>();
    for (let i = 0; i < routes.length; i++) {
        for (const s of routes[i]) {
            if (!stopToRoutes.has(s)) stopToRoutes.set(s, []);
            stopToRoutes.get(s)!.push(i);
        }
    }
    const visitedStops = new Set<number>([source]);
    const visitedRoutes = new Set<number>();
    let queue: number[] = [source];
    let buses = 0;
    while (queue.length > 0) {
        buses++;
        const next: number[] = [];
        for (const stop of queue) {
            for (const r of stopToRoutes.get(stop) ?? []) {
                if (visitedRoutes.has(r)) continue;
                visitedRoutes.add(r);
                for (const ns of routes[r]) {
                    if (ns === target) return buses;
                    if (!visitedStops.has(ns)) {
                        visitedStops.add(ns);
                        next.push(ns);
                    }
                }
            }
        }
        queue = next;
    }
    return -1;
}