Tarjan算法(割点&割边)
/ / 阅读耗时 15 分钟 本节探讨另一种Tarjan算法来求无向图的割点和割边。本文是这篇文章的延伸。
割点
首先认识什么是割点。
在一个连通无向图中，如果删去某一个点以及与其相连的边后图不再联通，则称这个点为一个割点。
Tarjan算法可以用来求割点，它的步骤与求强联通分量的算法十分相似，只是多了下面几个判断：
- 如果该点为搜索树的根结点（一个连通图搜索树有且仅有一个根结点），判断其子结点数目。如果子结点数目多于一个，说明两个子树只能通过根结点来往，由此判断根结点为割点。也就是说，根结点为割点的充要条件是子结点多于一个。
- 对于非根结点u，如果其有子结点并且存在某个子结点v的LOW值满足LOW[v]≥DFN[u]，则说明该子树上的结点不能访问父结点以上的结点，即父结点为割点。也就是说，非根结点为割点的充要条件是存在至少一个子结点满足LOW[v]≥DFN[u]。
求割点时不需要开栈，如果子结点已经被访问过，直接更新即可。
在求割点时，事实证明子结点是可以回溯到父结点的。但仍然建议在无向图中不允许子结点回溯父结点，这是为了与割边算法统一（见下文）。1
2
3
4
5
6
7
8
9
10
11
12void tarjan(int x, int last) {
DFN[x] = LOW[x] = cunt++;
for (int i = head[x]; i != -1; i = edge[i].next) {
if (!DFN[edge[i].to]) {
tarjan(edge[i].to, x), LOW[x] = min(LOW[x], LOW[edge[i].to]);
if (x != root && LOW[edge[i].to] >= DFN[x])Ans[x] = 1;
else if (x == root)c++;
} else if (edge[i].to != last)LOW[x] = min(LOW[x], DFN[edge[i].to]);
}
if (x == root && c >= 2)Ans[x] = 1;
}
注意：Tarjan算法得出的割点可能会重复。
割边
在一个连通无向图中，如果删去一条边后图不再连通，则该边为一条割边，也称为桥。
找割边的算法比割点容易，因为它不需要考虑根结点的问题。对于一条边(u，v)，u为父结点，则该边是割边的充要条件是LOW[v]>DFN[u]。这说明子结点不能通过其它边访问包含父结点在内的所有祖先结点，即父子边为割边。值得注意的是，判割边时，子结点不能回溯到父结点。1
2
3
4
5
6
7
8
9
10void tarjan(int x, int last) {
DFN[x] = LOW[x] = cunt++;
for (int i = head[x]; i != -1; i = edge[i].next) {
if (edge[i].to == last) continue;//不能回溯到父结点
if (!DFN[edge[i].to]) {
tarjan(edge[i].to, x), LOW[x] = min(LOW[x], LOW[edge[i].to]);
if (LOW[edge[i].to] > DFN[x])Ans[i] = 1;//标记边序号
} else if (edge[i].to != last)LOW[x] = min(LOW[x], DFN[edge[i].to]);
}
}
注意：如果一条边有重边，那么它一定不是割边。Tarjan算法不能排除重边的干扰，需要特判。
双连通分量
这里补充一下双连通分量的部分。
对于一个无向连通图，如果其不存在割点，那么称这两个点是点双连通的，简称双连通。
如果一个无向连通图中任何两个不同的点之间都是双连通的，那么称其为双连通图。对于一个无向图，其极大双连通子图称为双连通分量。
对于点双连通图来说，它有很多优秀的性质，下面提几个。
【性质I】一个点双连通图中，任何两个互异点之间都会有至少两条路径，它们经过的点（除去起点终点）交集为空。
对于这个性质，如果两个点之间的所有路径总需要经过一个点$p$，那么$p$是割点，这与双连通图矛盾。如果对于三条路径$l_1,l_2,l_3$，它们之间两两之间交集不为空，但是总交集为空，这种情况下总可以构造出另外两条路径使得它们交集为空。
另一个性质:
【性质II】点双连通图上任意两个互异点，都必然在一个环中。
这是显然的，由性质I很容易证明。
接下来是一个很有用的性质：
【性质III】若一个点双连通图上存在奇环，则其中所有点都可以放到一个奇环中。
一个不是很严谨的证明：
由于这是一个奇环， 它的点数不小于3。任取一个环外点$s$，它必然存在一条最短路径到达环上一点$v_1$，并且该路径除去$v_1$不存在环上其它的点。
由于这是双连通图，根据性质II，$s$至少有两条路径能够到达$v_1$，对于另一条路径，它必然与环上另一点有交集（否则说明$s$只能通过$v_1$到达环，这样$v_1$就是割点了），设该点为$v_2$。这样我们找到了从环外一点$x$，与$v_1,v_2$组成了环，并且与奇环的公共部分只有$v_1v_2$这一段路径，这样我们就会发现，$s$经过$v_1v_2$再回到$s$就有了两种方式（环），这两种环的奇偶性不同，即说明其中必有奇环。
点双连通分量可以使用tarjan算法求解。当我们找出一个割点时，将被割的子树（满足$LOW\geq DFN$）的子树点全部取出，再补充上割点（是补充，不用出栈），就能得到一个点双连通分量。这个算法基于一个事实，割点时划分双连通分量的点，并且割点至少存在于两个双连通分量中。
这里需要注意，求点双连通分量时，不用特判根节点。不特判根节点会导致根总是被识别成割点，但是需要注意到，根不是割点并且返回时，这已经是算法的最后一步了（最后一个连通分量），将根判成割点并不会影响答案。
例题POJ2942。它的思路就是求出补图后，判断哪些点不能放到一个奇环中。根据上面的性质III，我们可以求出它所有的点双连通分量，然后分别看其中是否存在奇环，若存在，则其上的点都必然在一个奇环中，判奇环可以使用二分图染色法。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
using namespace std;
struct Edge
{
int next, to;
} edge[2000005];
int op[N][N], head[N], cnt = 1, n, m, low[N], dfn[N], DFN, vis[N], in[N], c[N], C, ok[N], sv[N], flag;
int tmp[N], top;
stack<int> sta;
inline int read()
{
char e = getchar();
int s = 0;
while (e < '-') e = getchar();
while (e > '-') s = (s << 1) + (s << 3) + (e & 15), e = getchar();
return s;
}
inline void add(int x, int y)
{
edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}
void DFS(int x)//判断二分图的部分
{
for (int i = head[x]; i; i = edge[i].next) {
if (c[edge[i].to] == C) {
if (sv[edge[i].to] == -1) {
sv[edge[i].to] = sv[x] ^ 1, DFS(edge[i].to);
} else if (sv[edge[i].to] == sv[x])
flag = 0;
}
}
}
void tarjan(int x, int la)//不能回溯到父节点la
{
low[x] = dfn[x] = ++DFN, sta.push(x), in[x] = 1;
for (int i = head[x]; i; i = edge[i].next) {
if (edge[i].to == la) continue;
if (dfn[edge[i].to] == 0) {
tarjan(edge[i].to, x), low[x] = min(low[x], low[edge[i].to]);
if (low[edge[i].to] >= dfn[x]) {//有一个子节点low>=dfn
top = 0;
int to;
do {
to = sta.top(), c[to] = C, in[to] = 0, tmp[top++] = to, sv[to] = -1, sta.pop();
} while (to != edge[i].to);//该子树出栈，注意不是to!=x
c[x] = C, flag = 1, tmp[top++] = x, sv[x] = 0, DFS(x), ++C;//点x也需要加入双连通分量，但是不出栈
if (flag == 0) {
for (int j = 0; j < top; j++) ok[tmp[j]] = 1;
}
}
} else if (in[edge[i].to]) {
low[x] = min(low[x], dfn[edge[i].to]);
}
}
}
int main()
{
// DEBUG;
while (n = read(), m = read()) {
for (int i = 1; i <= n; i++) {
ok[i] = c[i] = in[i] = head[i] = vis[i] = low[i] = dfn[i] = 0;
for (int j = i + 1; j <= n; j++) op[i][j] = 0;
}
DFN = 0, cnt = 1, C = 1;
for (int i = 1, x, y; i <= m; i++) x = read(), y = read(), op[min(x, y)][max(x, y)] = 1;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (op[i][j] == 0) add(i, j), add(j, i);
}
}
for (int i = 1; i <= n; i++) tarjan(i, 0);
int ans = 0;
for (int i = 1; i <= n; i++) ans += ok[i] == 0;
printf("%d\n", ans);
}
return 0;