05 August 2008
求最少乘坐的公交车数
朴素单向BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
/*
https://leetcode.com/problems/bus-routes/discuss/122712/Simple-Java-Solution-using-BFS
BFS
*/
public int numBusesToDestination(int[][] routes, int S, int T) {
HashSet<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
int result = 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);
}
}
queue.offer(S);
while (!queue.isEmpty()) {
int len = queue.size();
result++;
for (int i = 0; i < len; i++) {
int cur = queue.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 result;
}
queue.offer(routes[bus][j]);
}
}
}
}
return -1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
int s, t;
int[][] rs;
public int numBusesToDestination(int[][] _rs, int _s, int _t) {
rs = _rs;
s = _s;
t = _t;
if (s == t) return 0;
int ans = bfs();
return ans;
}
int bfs() {
// 记录某个车站可以进入的路线
Map<Integer, Set<Integer>> map = new HashMap<>();
// 队列存的是经过的路线
Deque<Integer> d = new ArrayDeque<>();
// 哈希表记录的进入该路线所使用的距离
Map<Integer, Integer> m = new HashMap<>();
int n = rs.length;
for (int i = 0; i < n; i++) {
for (int station : rs[i]) {
// 将从起点可以进入的路线加入队列
if (station == s) {
d.addLast(i);
m.put(i, 1);
}
Set<Integer> set = map.getOrDefault(station, new HashSet<>());
set.add(i);
map.put(station, set);
}
}
while (!d.isEmpty()) {
// 取出当前所在的路线，与进入该路线所花费的距离
int poll = d.pollFirst();
int step = m.get(poll);
// 遍历该路线所包含的车站
for (int station : rs[poll]) {
// 如果包含终点，返回进入该路线花费的距离即可
if (station == t) return step;
// 将由该线路的车站发起的路线，加入队列
Set<Integer> lines = map.get(station);
if (lines == null) continue;
for (int nr : lines) {
if (!m.containsKey(nr)) {
m.put(nr, step + 1);
d.add(nr);
}
}
}
}
return -1;
}
}
双向BFS（并查集预处理无解情况）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
class Solution {
static int N = (int) 1e6 + 10;
static int[] p = new int[N];
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void union(int a, int b) {
p[find(a)] = p[find(b)];
}
boolean query(int a, int b) {
return find(a) == find(b);
}
int s, t;
int[][] rs;
public int numBusesToDestination(int[][] _rs, int _s, int _t) {
rs = _rs;
s = _s;
t = _t;
if (s == t) return 0;
for (int i = 0; i < N; i++) p[i] = i;
for (int[] r : rs) {
for (int loc : r) {
union(loc, r[0]);
}
}
if (!query(s, t)) return -1;
int ans = bfs();
return ans;
}
// 记录某个车站可以进入的路线
Map<Integer, Set<Integer>> map = new HashMap<>();
int bfs() {
Deque<Integer> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
Map<Integer, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
int n = rs.length;
for (int i = 0; i < n; i++) {
for (int station : rs[i]) {
// 将从起点可以进入的路线加入正向队列
if (station == s) {
d1.addLast(i);
m1.put(i, 1);
}
// 将从终点可以进入的路线加入反向队列
if (station == t) {
d2.addLast(i);
m2.put(i, 1);
}
Set<Integer> set = map.getOrDefault(station, new HashSet<>());
set.add(i);
map.put(station, set);
}
}
// 如果「起点所发起的路线」和「终点所发起的路线」有交集，直接返回 1
Set<Integer> s1 = map.get(s), s2 = map.get(t);
Set<Integer> tot = new HashSet<>();
tot.addAll(s1);
tot.retainAll(s2);
if (!tot.isEmpty()) return 1;
// 双向 BFS
while (!d1.isEmpty() && !d2.isEmpty()) {
int res = -1;
if (d1.size() <= d2.size()) {
res = update(d1, m1, m2);
} else {
res = update(d2, m2, m1);
}
if (res != -1) return res;
}
return 0x3f3f3f3f; // never
}
int update(Deque<Integer> d, Map<Integer, Integer> cur, Map<Integer, Integer> other) {
// 取出当前所在的路线，与进入该路线所花费的距离
int poll = d.pollFirst();
int step = cur.get(poll);
// 遍历该路线所包含的车站
for (int station : rs[poll]) {
// 遍历将由该线路的车站发起的路线
Set<Integer> lines = map.get(station);
if (lines == null) continue;
for (int nr : lines) {
if (cur.containsKey(nr)) continue;
if (other.containsKey(nr)) return step + other.get(nr);
cur.put(nr, step + 1);
d.add(nr);
}
}
return -1;
}
}