-
Notifications
You must be signed in to change notification settings - Fork 2
/
FindBridges.java
56 lines (46 loc) · 1.21 KB
/
FindBridges.java
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
package com.github.datastructureandalgorithm.graph.chapter8;
import java.util.ArrayList;
import java.util.List;
public class FindBridges {
private Graph G;
private boolean[] visited;
private int[] ord;
private int[] low;
private int cnt;
private List<Edge> res;
public FindBridges(Graph G) {
this.G = G;
visited = new boolean[G.V()];
ord = new int[G.V()];
low = new int[G.V()];
res = new ArrayList<>();
for (int v = 0; v < G.V(); v++)
if (!visited[v])
dfs(v, v);
}
/**
* 对图进行深度优先遍历
*
* @param v
*/
private void dfs(int v, int parent) {
visited[v] = true;
ord[v] = cnt;
low[v] = ord[v];
cnt++;
for (int w : G.adj(v)) {
if (!visited[w]) {
dfs(w, v);
low[v] = Math.min(low[w], low[v]);
if (low[w] > ord[v])
// v-w is a bridge
res.add(new Edge(v, w));
} else if (w != parent) {
low[v] = Math.min(low[w], low[v]);
}
}
}
public List<Edge> result() {
return res;
}
}