Tarjan是个好东西
求强连通分量，可以用来缩点等等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| int stack[N], dfn[N], low[N], col[N];
bool vis[N];
void Tarjan(int u) {
dfn[u] = low[u] = ++tot;
stack[++top] = u;
vis[u] = true;
int v;
for (int i = head[u]; i; i = e[i].nxt) {
v = e[i].to;
if (!dfn[v])
Tarjan(v), low[u] = min(low[u], low[v]);
else if (vis[v])
low[u] = min(low[u], low[v]);
}
if (dfn[u] == low[u]) {
scc++;
do {
v = stack[top--];
vis[v] = false;
col[v] = scc;
}
while (v != u);
}
}
|
搞出强连通分量后，重新建图，该干啥干啥
P2515
T103252
P2746
割点
和求强连通分量不太一样
low[x]表示 \(dfs\) 下去最早遇到的割点
当 \(v\) 已经访问过时，用 \(dfn[v]\) 更新 \(low[u]\) （为什么？画两个连环就知道了）
当 \(u\) 为根时只要统计子树个数即可
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, int rt) {
dfn[u] = low[u] = ++tot;
int v, ch = 0;
for (int i = head[u]; i; i = e[i].nxt) {
v = e[i].to;
if (!dfn[v]) {
Tarjan(v, rt), low[u] = min(low[u], low[v]);
if (u != rt && low[v] >= dfn[u])
cut[u] = true;
if (u == rt)
ch++;
}
low[u] = min(low[u], dfn[v]);
}
if (u == rt && ch >= 2)
cut[u] = true;
}
for (int i = 1; i <= n; ++i)
if (!dfn[i])
Tarjan(i, i);
|