https://leetcode-cn.com/submissions/detail/25642457/
class Solution {
public int numBusesToDestination(int[][] routes, int S, int T) {
if (S == T) { // 如果起点 == 终点 return
return 0;
}
// 根据公交车节点和公交站点节点建立关系
Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
for (int i = 0; i< routes.length; ++ i) {
for (int j: routes[i]) { // j = 公交站点
if (!map.containsKey(j)) { // 不包含的公交站点则加入 map
map.put(j, new HashSet<Integer>()); // 默认初始值为0
}
map.get(j).add(i);
}
}
// 从起点开始, 吧所有符合公交车站点节点S的对应公交车加入queue中
Queue<Integer> queue = new LinkedList<Integer>();
Set<Integer> visited = new HashSet<Integer>();
for (int st: map.get(S)) {
queue.offer(st);
visited.add(st);
}
int ans = 1;
while(!queue.isEmpty()) {// 知道队列为空
Queue<Integer> t = new LinkedList<Integer>();
while(!queue.isEmpty()) {
int currentCar = queue.poll();
for (int k: routes[currentCar]) {// 遍历链接的公交车站节点
if (k == T) {
return ans;
}
for (int nextCar : map.get(k)) { // 便利当前公交车站点所有的公交车借点
if (!visited.contains(nextCar)) {// 未访问过的
t.offer(nextCar);
visited.add(nextCar);
}
}
}
}
++ ans;
queue = t;
}
return -1;
}
}
