815. Bus Routes

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) {
            return 0;
        }

        int buses = 1;
        boolean[] visited = new boolean[routes.length];
        Map<Integer, Set<Integer>> stationToLineSetMap = new HashMap<>();

        // 路线的队列
        Queue<Integer> queue = new LinkedList<>();

        for (int lineIndex = 0; lineIndex < routes.length; lineIndex++) {
            for (int station : routes[lineIndex]) {
                if (station == source) {
                    // source 位于此条路线上，把这条路线加入队列进行 BFS 搜索
                    queue.offer(lineIndex);
                    visited[lineIndex] = true;
                }

                stationToLineSetMap.computeIfAbsent(station, key -> new HashSet<>()).add(lineIndex);
            }
        }

        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                int lineIndex = queue.poll();

                // 线路上有多个站点，尝试从这些站点进入下一条线路
                for (int station : routes[lineIndex]) {
                    if (station == target) {
                        return buses;
                    }

                    for (int line : stationToLineSetMap.get(station)) {
                        if (visited[line]) {
                            continue;
                        }
                        
                        queue.offer(line);
                        visited[line] = true;
                    }
                }
            }

            buses++;
        }

        return -1;
    }
}

关键解题思路：对路线进行 BFS 遍历，遍历过程中检查站点是否满足条件。

References

815. Bus Routes