0%

Tarjan 学习笔记

From《算法竞赛进阶指南》。

一些概念

  • 割点:无向图连通中,删去点 x 与 x 相连的边后 G 不连通,则 x 为 G 的割点。
  • 割边:无向图连通中,删去边 e 后 G 不连通,则 e 称为 G 的桥或割边。
  • 点双连通:若一张无向连通图不存在割点(点连通度等于一),则称它为点双连通。
  • 边双连通:若一张无向连通图不存在桥(边连通度等于一),则称它为边双连通。
  • 点双连通分量(v-DCC):无向图的极大点双连通子图。
  • 边双连通分量(e-DCC):无向图的极大边双连通子图。

Tarjan 算法可以求:

  1. 割点、割边
  2. 无向图的双连通分量
  3. 有向图的强连通分量

Tarjan 算法中的 low:

low[x] 为以下节点 dfn 的最小值:

  1. subtree(x) 中的节点。
  2. 通过一条不在搜索树上的边,能够到达 subtree(x) 的节点。

若 (x, y) 在搜索树上,则 $low[x] = \min(low[x], low[y])$
若 (x, y) 不在搜索树上,则 $low[x] = \min(low[x], dfn[y])$

Tarjan 求割边

无向边 (x, y) 是桥,当且仅当搜索树上存在 x 的一个子节点 y,满足:
$dfn[x] < low[y]$

桥一定是搜索树中的边,并且一个简单环中的边一定都不是桥。

注意求桥的时候可能出现重边,因此此时 fa 的 dfn 可能会更新 low[x]。因此我们采用成对编号边的方法。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 100000 + 5;

int n, m, tot = 1, head[N], to[N * 2], nxt[N * 2];
int dfn[N], low[N], cnt, bridge[N];

void AddEdge(int u, int v)
{
nxt[++tot] = head[u], head[u] = tot, to[tot] = v;
}

void Tarjan(int u, int lst)
{
dfn[u] = low[u] = ++cnt;
for (int e = head[u]; e; e = nxt[e])
{
int v = to[e];
if (!dfn[v])
{
Tarjan(v, e);
low[u] = min(low[u], low[v]);
if (dfn[u] < low[v]) bridge[e] = bridge[e ^ 1] = 1;
}
else if (e != (lst ^ 1)) low[u] = min(low[u], dfn[v]);
}
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
AddEdge(u, v), AddEdge(v, u);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) Tarjan(i, 0);
for (int i = 2; i < tot; i += 2)
if (bridge[i]) printf("%d %d\n", to[i ^ 1], to[i]);
return 0;
}

Tarjan 求割点

若 x 不是搜索树的根节点,则 x 是割点当且仅当搜索树上存在一个 x 的子节点 y,满足:
$dfn[x] \leq low[y]$

若 x 是搜索树的根节点,则要存在两个子节点满足上述条件。

求割点时不需要考虑父节点和重边的问题。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 100000 + 5;

int n, m, tot = 1, head[N], to[N * 2], nxt[N * 2];
int dfn[N], low[N], cnt, cut[N], stk[N], rt;

void AddEdge(int u, int v)
{
nxt[++tot] = head[u], head[u] = tot, to[tot] = v;
}

void Tarjan(int u)
{
dfn[u] = low[u] = ++cnt;
int flag = 0;
for (int e = head[u]; e; e = nxt[e])
{
int v = to[e];
if (!dfn[v])
{
Tarjan(v);
low[u] = min(low[u], low[v]);
if (dfn[u] <= low[v])
{
flag++;
if (u != rt || flag > 1) cut[u] = 1;
}
}
else low[u] = min(low[u], dfn[v]);
}
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
if (u == v) continue;
AddEdge(u, v), AddEdge(v, u);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) rt = i, Tarjan(i);
for (int i = 1; i <= n; i++)
if (cut[i]) printf("%d\n", i);
return 0;
}

Tarjan 求点双连通分量

定理

定理:一张无向连通图是点双连通图,当且仅当图的顶点数不超过 2 或者任意两点都同时包含在至少一个简单环中。“简单环”是指不自交的环。

证明:假设图中顶点数不小于 3。

充分性显然。

必要性:反证法。假设图是点双连通图,并且存在两点 x, y, 它们不同时处于一个简单环中。
如果 x, y 之间仅存在 1 条简单路径,那么路径上至少有一个割点,与“点双连通”矛盾。
如果 x, y 之间存在 2 条或以上的简单路径,那么可以发现,任意两条都至少有一个除 x, y 之外的交点;进一步可以推导出,x, y 之间的所有路径必定同时交于除 x, y 之外的某一点 p(不然就会存在两条没有交点的路径,形成一个简单环)。根据定义,p 是一个割点,与“点双连通”矛盾,故假设不成立。

求点双连通分量

割点可能属于多个点双连通分量。

在 Tarjan 算法过程中维护一个栈。
当找到一个点使得 $dfn[x] \leq low[y]$ 时,从栈顶不断弹出节点,直到弹出 y 为止。弹出的节点与 x 一起构成一个 v-DCC。

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
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int N = 100000 + 5;

int n, m, tot = 1, head[N], to[N * 2], nxt[N * 2];
int dfn[N], low[N], cnt, cut[N], stk[N], top, rt, num;

vector<int> dcc[N];

void AddEdge(int u, int v)
{
nxt[++tot] = head[u], head[u] = tot, to[tot] = v;
}

void Tarjan(int u)
{
dfn[u] = low[u] = ++cnt;
stk[++top] = u;
if (u == rt && head[u] == 0)
{
dcc[++num].pb(u);
return;
}
int flag = 0;
for (int e = head[u]; e; e = nxt[e])
{
int v = to[e];
if (!dfn[v])
{
Tarjan(v);
low[u] = min(low[u], low[v]);
if (dfn[u] <= low[v])
{
flag++;
if (u != rt || flag > 1) cut[u] = 1;
num++;
int w;
do
{
w = stk[top--];
dcc[num].pb(w);
} while (w != v);
dcc[num].pb(u);
}
}
else low[u] = min(low[u], dfn[v]);
}
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
if (u == v) continue;
AddEdge(u, v), AddEdge(v, u);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) rt = i, Tarjan(i);
printf("dcc = %d\n", num);
for (int i = 1; i <= num; i++)
{
printf("v-DCC #%d:", i);
for (int j = 0; j < dcc[i].size(); j++) printf(" %d", dcc[i][j]);
printf("\n");
}
return 0;
}

v-DCC 的缩点

设图中包含 p 个割点和 t 个 v-DCC。我们建立一张包含 p + t 个节点的新图,在每个割点与包含它的所有 v-DCC 间连边。这样得到的新图是一棵树(或森林)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
cnt = num;
for (int i = 1; i <= n; i++)
if (cut[i]) id[i] = ++cnt;
tc = 1;
for (int i = 1; i <= num; i++)
for (int j = 0; j < dcc[i].size(); j++)
{
int x = dcc[i][j];
if (cut[x])
{
Add_c(i, id[x]);
Add_c(id[x], c);
}
else c[x] = i;
}

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
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
#include <bits/stdc++.h>
using namespace std;

const int N = 100000 + 5;

int n, m, tot = 1, head[N], to[N * 2], nxt[N * 2];
int dfn[N], low[N], cnt, bridge[N], c[N], dcc;

void AddEdge(int u, int v)
{
nxt[++tot] = head[u], head[u] = tot, to[tot] = v;
}

void Tarjan(int u, int lst)
{
dfn[u] = low[u] = ++cnt;
for (int e = head[u]; e; e = nxt[e])
{
int v = to[e];
if (!dfn[v])
{
Tarjan(v, e);
low[u] = min(low[u], low[v]);
if (dfn[u] < low[v]) bridge[e] = bridge[e ^ 1] = 1;
}
else if (e != (lst ^ 1)) low[u] = min(low[u], dfn[v]);
}
}

void DFS(int u)
{
c[u] = dcc;
for (int e = head[u]; e; e = nxt[e])
{
int v = to[e];
if (c[v] || bridge[e]) continue;
DFS(v);
}
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
AddEdge(u, v), AddEdge(v, u);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) Tarjan(i, 0);
for (int i = 1; i <= n; i++)
if (!c[i]) ++dcc, DFS(i);
printf("dcc = %d\n", dcc);
for (int i = 1; i <= n; i++) printf("%d belongs to DCC %d\n", i, c[i]);
return 0;
}

e-DCC 的缩点

把每个 e-DCC 看作一个节点,把桥边看做连接 c[x] 与 d[x] 的无向边,会产生一棵树(或森林)。

1
2
3
4
5
6
7
8
9
10
11
12
13
int hc[N], toc[N * 2], nc[N * 2], tc = 1;

void Add_c(int u, int v)
{
nc[++tc] = hc[u], hc[u] = tc, toc[tc] = v;
}

for (int i = 2; i <= tot; i++)
{
int u = to[i ^ 1], v = to[i];
if (c[u] == c[v]) continue;
Add_c(c[u], c[v]);
}