# 0815. Bus Routes
###### tags: `Leetcode` `Hard` `BFS`
Link: https://leetcode.com/problems/bus-routes/
## 思路
可以理解成每一个node是一个bus station
每个bus station的children是能去的所有bus station
如果建的图是每一站能去的所有站(不是bus station)的会导致TLE 因为每一bus station有很多点 我们在记录每个站能到的所有点的时候已经把这一个bus station的所有站都加进去了 所以每次access到这个bus station的一个点 都要把整个bus station能到的所有站都遍历一遍
## Code

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for(int i=0; i<routes.length; i++){
            for(int j=0; j<routes[i].length; j++){
                if(!graph.containsKey(routes[i][j])) graph.put(routes[i][j], new HashSet<>());
                graph.get(routes[i][j]).add(i);
            }
        }
        
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> q = new LinkedList<>();
        q.add(source);
        int step = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                int curr = q.poll();
                if(curr==target) return step;
                for(int next:graph.get(curr)){
                    if(visited.contains(next)) continue;
                    visited.add(next);
                    for(int j=0; j<routes[next].length; j++) q.offer(routes[next][j]);  
                }
            }
            step++;
        }
        return -1;
    }
}