815. 公交路线

注意层次遍历，队列会动态增加

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if(source == target) return 0;
        Queue<Integer> queue = new LinkedList<>();
        int res = 0;
        Map<Integer, List<Integer>> map = new HashMap<>();
        Set<Integer> set = new HashSet<>();
        for(int i=0; i<routes.length; i++) {
            for(int val: routes[i]) {
                List<Integer> temp = map.getOrDefault(val, new ArrayList<>());
                temp.add(i);
                map.put(val, temp);
            }
        } 
        queue.add(source);
        while(!queue.isEmpty()) {
            res++;
            //注意queue会动态增加
            for (int i = queue.size(); i > 0; --i) {
                int poll = queue.poll();
                List<Integer> temp = map.getOrDefault(poll, new ArrayList<>());
                for(Integer val: temp) {
                    if(set.contains(val)) {
                        continue;
                    }
                    set.add(val);
                    for(int k = 0; k<routes[val].length; k++) {  
                        if(routes[val][k] == target) {
                            return res;
                        }
                        queue.add(routes[val][k]);           
                    }
                }
            }
        }
        return -1;
    }
}