公交路线

/*
 * 思路：
 * 1. 使用广度优先搜索（BFS）来寻找最短路径。
 * 2. 创建一个映射，将每个车站映射到经过该车站的公交车集合。
 * 3. 使用队列进行BFS，记录访问过的车站和公交车。
 * 4. 每次从队列中取出一个车站，遍历经过该车站的所有公交车。
 * 5. 对于每辆公交车，遍历其所有经过的车站，如果是目标车站，返回当前乘坐公交车的数量。
 * 6. 如果所有可能性都遍历完还没找到目标车站，返回-1。
 */
import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) return 0;
        Map<Integer, Set<Integer>> stationToBuses = Arrays.stream(routes)
            .flatMapToInt(Arrays::stream)
            .boxed()
            .distinct()
            .collect(Collectors.toMap(
                station -> station,
                station -> new HashSet<>(),
                (a, b) -> a,
                HashMap::new
            ));
        for (int bus = 0; bus < routes.length; bus++) {
            for (int station : routes[bus]) {
                stationToBuses.get(station).add(bus);
            }
        }
        Queue<int[]> queue = new LinkedList<>();
        Set<Integer> visitedStations = new HashSet<>();
        Set<Integer> visitedBuses = new HashSet<>();
        queue.offer(new int[]{source, 0});
        visitedStations.add(source);
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int station = current[0];
            int buses = current[1];
            for (int bus : stationToBuses.getOrDefault(station, new HashSet<>())) {
                if (visitedBuses.contains(bus)) continue;
                visitedBuses.add(bus);
                for (int nextStation : routes[bus]) {
                    if (nextStation == target) return buses + 1;
                    if (visitedStations.contains(nextStation)) continue;
                    visitedStations.add(nextStation);
                    queue.offer(new int[]{nextStation, buses + 1});
                }
            }
        }
        return -1;
    }
}