-
Notifications
You must be signed in to change notification settings - Fork 0
/
LowLink.java
79 lines (76 loc) · 2.54 KB
/
LowLink.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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package graph;
/**
* @verified
* - http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_A
* - http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B
*
* @param <Edg> type of edge
*/
public class LowLink<Edg extends AbstractEdge> {
final int N;
final int[] Ord;
final int[] Low;
final int[] Par;
final java.util.ArrayList<Integer> Articulation;
final java.util.ArrayList<Edg> Bridge;
public LowLink(Graph<Edg> g) {
this.Articulation = new java.util.ArrayList<>();
this.Bridge = new java.util.ArrayList<>();
this.N = g.getV();
this.Ord = new int[N];
this.Low = new int[N];
this.Par = new int[N];
build(g);
}
public java.util.ArrayList<Integer> getArticulations() {
return Articulation;
}
public java.util.ArrayList<Edg> getBridges() {
return Bridge;
}
private void build(Graph<Edg> g) {
int nowOrd = 0;
java.util.Arrays.fill(Ord, -1);
long[] stack = new long[N];
int ptr = 0;
for (int i = 0; i < N; i++) {
if (Ord[i] >= 0) continue;
Par[i] = -1;
stack[ptr++] = 0l << 32 | i;
while (ptr > 0) {
long p = stack[--ptr];
int u = (int) (p & 0xffff_ffffl);
int j = (int) (p >>> 32);
if (j == 0) {
Low[u] = Ord[u] = nowOrd++;
}
if (j < g.deg(u)) {
int v = g.getEdge(u, j).to;
stack[ptr++] += 1l << 32;
if (v == Par[u]) continue;
if (Ord[v] == -1) {
stack[ptr++] = 0l << 32 | v;
Par[v] = u;
} else {
Low[u] = Math.min(Low[u], Ord[v]);
}
} else {
boolean isArticulation = false;
int cnt = 0;
while (j --> 0) {
Edg e = g.getEdge(u, j);
int v = e.to;
if (Par[v] == u) {
Low[u] = Math.min(Low[u], Low[v]);
cnt++;
isArticulation |= u != i && Ord[u] <= Low[v];
if (Ord[u] < Low[v]) Bridge.add(e);
}
}
isArticulation |= u == i && cnt > 1;
if (isArticulation) Articulation.add(u);
}
}
}
}
}