-
Notifications
You must be signed in to change notification settings - Fork 0
/
articulationPoints.java
35 lines (35 loc) · 1.17 KB
/
articulationPoints.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
public class articulationPoints {
ArrayList<Integer>[] g;
int[] low;
int[] dfsNum;
int[] maxLow; // max of low values of all child in dfs tree
boolean[] visit;
int currentNum = 0;
articulationPoints(int N){
g = new ArrayList[N];
low = new int[N];
maxLow = new int[N];
dfsNum = new int[N];
visit = new boolean[N];
for(int i = 0; i < N; i++){g[i] = new ArrayList<>();}
}
void dfs(int u, int parent){
visit[u] = true;
dfsNum[u] = low[u] = currentNum++;
for(int v : g[u]){
if(visit[v]){
if(v == parent) continue;
low[u] = Math.min(low[u], dfsNum[v]); //back - edge
}
else{
dfs(v, u);
low[u] = Math.min(low[u], low[v]);
// if(low[v] > dfsNum[u]) then u -- v is a bridge
maxLow[u] = Math.max(maxLow[u], low[v]);
// if (maxLow[u] >= dfsNum[u]) then u is an articulation point
//[Note - this is for except the root of dfs tree]
// for root child > 1
}
}
}
}