😫815 Bus Routes

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        // stop -> buses that go through this stop
        Map<Integer, Set<Integer>> stopBuses = new HashMap<>();
        for (int i = 0; i < routes.length; i++) {
            for (int stop : routes[i]) {
                Set<Integer> buses = stopBuses.get(stop);
                if (buses == null) {
                    buses = new HashSet<>();
                }
                buses.add(i);
                stopBuses.put(stop, buses);
            }
        }
        int len = 0;
        Queue<Integer> queue = new ArrayDeque<>();
        Set<Integer> visited = new HashSet<>();
        
        queue.offer(source);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int s = 0; s < size; s++) {
                int stop = queue.poll();
                if (stop == target) {
                    return len;
                }
                // if (visited.contains(stop)) {
                //     continue;
                // }
                // visited.add(stop);
                Set<Integer> buses = stopBuses.get(stop);
                for (int bus : buses) {
                    if (visited.contains(bus)) {
                        continue;
                    }
                    //???
                    visited.add(bus);
                    int[] route = routes[bus];
                    for (int i = 0; i < route.length; i++) {
                        // if (visited.contains(route[i])) {
                        //     continue;
                        // }
                        if (route[i] == target) {
                            return len + 1;
                        }
                        queue.offer(route[i]);
                    }
                }
            }
            len++;
        }
        return -1;
    }
}

好奇怪的题，感觉大概方向是对的，但是去重方式不对会导致tle，这里似乎是允许stop重复，但是不允许bus重复，也就是你可以去某个stop再回来，但是你不能在两次坐一样的bus，我感觉是如果两次坐一样的bus会死循环 以下是参考的解法

class Solution {
    public int numBusesToDestination(int[][] routes, int S, int T) {
       HashSet<Integer> visited = new HashSet<>();
       Queue<Integer> q = new LinkedList<>();
       HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
       int ret = 0; 
        
       if (S==T) return 0; 
        
       for(int i = 0; i < routes.length; i++){
            for(int j = 0; j < routes[i].length; j++){
                ArrayList<Integer> buses = map.getOrDefault(routes[i][j], new ArrayList<>());
                buses.add(i);
                map.put(routes[i][j], buses);                
            }       
        }
                
       q.offer(S); 
       while (!q.isEmpty()) {
           int len = q.size();
           ret++;
           for (int i = 0; i < len; i++) {
               int cur = q.poll();
               ArrayList<Integer> buses = map.get(cur);
               for (int bus: buses) {
                    if (visited.contains(bus)) continue;
                    visited.add(bus);
                    for (int j = 0; j < routes[bus].length; j++) {
                        if (routes[bus][j] == T) return ret;
                        q.offer(routes[bus][j]);  
                   }
               }
           }
        }
        return -1;
    }
}