tarjan算法求SCC/BCC

tarjan算法求SCC/BCC

SCC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void tarjan(int u) {
dfn[u] = low[u] = ++order;
st.push(u);
for(int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if(!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if(dfn[v] < dfn[u]) {
low[u] = min(low[u], dfn[v]);
}
}
if(dfn[u] == low[u]) {
int num = 0, tmp;
do {
tmp = st.top();
st.pop();
num++;
}while(tmp != u);
mx = max(mx, num);
}
}

割点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++order;
int child = 0;
for(int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if(v == fa) continue;
if(!dfn[v]) {
child++;
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u] && fa) {
if(!point[u]) point[u] = true, ans++;
} else if(!fa && child > 1) {
if(!point[u]) point[u] = true, ans++;
}
} else if(dfn[v] < dfn[u]) {
low[u] = min(low[u], dfn[v]);
}
}
}

点双连通分量

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
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++order;
for(int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if(v == fa) continue;
if(!dfn[v]) {
int id = e[i].index;
st.push(id);
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u]) {
num++;
mn[num] = INF;
int tmp;
do {
tmp = st.top();
belong[tmp] = num;
st.pop();
mn[num] = min(mn[num], tmp);
}while(tmp != id);
}
} else if(dfn[v] < dfn[u]) {
st.push(e[i].index);
low[u] = min(low[u], dfn[v]);
}
}
}

边双连通分量及桥

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
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++order;
bool flag = true;
st.push(u);
for(int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if(v == fa && flag) {
flag = false;
continue;
}
if(!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] > dfn[u]) {
bridge[i] = 1;
if(i & 1) bridge[i + 1] = 1;
else bridge[i - 1] = 1;
}
} else if(dfn[v] < dfn[u]) {
low[u] = min(low[u], dfn[v]);
}
}
if(dfn[u] == low[u]) {
num++;
int tmp;
do{
tmp = st.top();
belong[tmp] = num;
st.pop();
}while(tmp != u);
}
}
#

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×