P8435 【模板】点双连通分量题解

2022.7.28 更新：改正一处笔误。

# Tarjan 算法与割点

### 概念

给定无向图 $G=(V,E)$：

若对于 $x\in V$，从图中删去节点 $x$ 以及所有与 $x$ 关联的边之后，$G$ 分裂成两个或两个以上不相连的子图，则称 $x$ 为 $G$ 的**割点**。

一般无向图（不一定连通）的割点就是它的各个连通块的割点。

而由著名计算机科学家 Robert Tarjan 的名字命名的 Tarjan 算法能够在线性时间内求出无向图的割点，进一步可求出无向图的双连通分量。 Tarjan 算法基于无向图的深度优先遍历，下面介绍一些相关概念。

#### 时间戳

在图的深度优先遍历过程中，按照每个节点第一次被访问的时间顺序，依次给予 $N$ 个节点从 $1$ 到 $N$ 的整数标记，该标记称为**时间戳**，记为 $dfn_x$。

#### 搜索树

在无向图中任选一个节点出发进行深度优先遍历，每个点只访问一次。所有发生递归的边 $(x,y)$（换言之，从 $x$ 到 $y$ 是对 $y$ 的第一次访问）构成一棵树。我们把它称为**无向连通图的搜索树**。当然，一般无向图（不一定连通）的各个连通块的搜索树构成无向图的搜索森林。

下图左侧展示了一张无向连通图，灰色节点是深度优先遍历的起点，加粗的边是发生递归的边（假设我们在遇到多个分支时，总是优先访问最靠左的一条）。右侧展示了深度优先遍历的搜索树，并标注了节点的时间戳。

![](https://cdn.luogu.com.cn/upload/image_hosting/ryswqep8.png)

#### 追溯值

除了时间戳之外， Tarjan 算法还引入了一个**追溯值** $low_x$。设 $subtree(x)$ 表示搜索树中以 $x$ 为根的子树。$low_x$ 定义为以下节点的时间戳的最小值：

1. $subtree(x)$ 中的节点。

1. 通过 $1$ 条**不在搜索树上的边**，能够到达 $subtree(x)$ 的节点。

以上图为例。为了叙述简便，我们用时间戳代表节点编号。$subtree(2)=\{2,3,4,5\}$。另外，节点 $1$ 通过不在搜索树上的边 $(1,5)$ 能够到达 $subtree(2)$。所以 $low_2=1$。

### 求法

根据定义，为了计算 $low_x$，应该先令 $low_x=dfn_x$，然后考虑从 $x$ 出发的每条边 $(x,y)$：

若在搜索树上 $x$ 是 $y$ 的父节点，则令 $low_x=\min(low_x,low_y)$。

若无向边 $(x,y)$ 不是搜索树上的边，则令 $low_x=\min(low_x,dfn_y)$。

下图中括号里的数值标注了每个节点的追溯值 $low$。

![](https://cdn.luogu.com.cn/upload/image_hosting/bt771s0u.png)

#### 割点判定法则

若 $x$ 不是搜索树的根节点（深度优先遍历的起点），则 $x$ 是割点当且仅当搜索树上存在 $x$ 的一个子节点 $y$，满足：

$\hspace{15.0em}$ $dfn_x\le low_y$

特别地，若 $x$ 是搜索树的根节点，则 $x$ 是割点当且仅当搜索树上存在**至少两个**子节点 $y1,y2$ 满足上述条件。

#### 证明：

根据定义，$dfn_x\le low_y$ 说明从 $subtree(y)$ 出发，无论如何也无法到达比 $x$ 更早访问的节点。换句话说，只有节点 $x$ 上有若干条边通向 $subtree(y)$，$x$ 便是它通向外界的唯一通道，$suntree(y)$ 中所有节点的 $dfn$ 都必须大于等于它， 而不能小于它。断开节点 $x$ 后，$subtree(y)$ 好像形成了一个封闭的环境，没有边与比 $x$ 更早的节点相连，图断开成了两部分，因此 $x$ 是割点。

反之，若不存在子节点 $y$，使得 $dfn_x\le low_y$，则说明每个 $subtree(y)$ 都能绕行其他边到达比 $x$ 更早访问的节点，$x$ 自然不是割点。

对于根节点 $x$，若想分为两个及以上不相连的子图，自然是需要两个及以上不相连的子树才能办到。

_证毕。_

在上图中，共有两个割点，分别是时间戳为 $1$ 和 $6$ 的两个点。

下面的程序求出一张无向图中所有的割点。因为割点判定法则是小于等于号，所以在求割点时，不必考虑父节点和重边的问题，从 $x$ 出发能访问到的所有点的时间戳都可以用来更新 $low_x$。

```cpp

const int SIZE = 100010;
int head[SIZE], ver[SIZE * 2], Next[SIZE * 2];
int dfn[SIZE], low[SIZE], stack[N];
int n, m, tot = 1, num, root;
bool cut[SIZE];
void add(int x, int y) { // 邻接表存图
	ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}
void tarjan(int x) { 
	dfn[x] = low[x] = ++num; //按照访问顺序初始化 x 节点的 dfn 与 low 值
	int flag = 0;
	for (int i = head[x]; i; i = Next[i]) {
		int y = ver[i];
		if (!dfn[y]) {
			tarjan(y);
			low[x] = min(low[x], low[y]);
			if (low[y] >= dfn[x]) {
				flag++;
				if (x != root || flag > 1) cut[x] = true;//割点判定法则
			}
		} 
		else
			low[x] = min(low[x], dfn[y]);
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (register int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		if (x == y)
			continue;
		add(x, y), add(y, x);//正反向存边
	}
	for (register int i = 1; i <= n; i++)
		if (!dfn[i])
			root = i, tarjan(i);
	return 0;
}

```

### 练习

[P3388 割点](https://www.luogu.com.cn/problem/P3388)

[P3469 [POI2008]BLO-Blockade](https://www.luogu.com.cn/problem/P3469)

# 点双连通分量
### 概念

若一张无向连通图不存在割点，则称它为**点双连通图**。

无向图的**极大**点双联通子图被称为**点双联通分量**，简记为 **v-DCC**。

在上面的定义中，我们称一个双连通子图 $G'=(V',E')$ “极大（其中 $V'\subseteq V, E'\subseteq E$），是指不存在包含 $G'$ 的更大的子图 $G''=(V'',E'')$，满足 $V'\subseteq V''\subseteq V$， $E' \subseteq E''\subseteq E$ 并且 $G''$ 也是双连通子图。

### 定理

一张无向图是点双连通图，当且仅当满足下列**两个条件之一**：

1. 图的顶点数不超过 $2$。

1. 图中任意两点都同时包含在**至少一个**简单环中。其中“简单环”指的是不自交的环，也就是我们通常画出的环。

#### 证明：
对于顶点数不超过 $2$ 的情况，定理显然成立，下面假设图中顶点数不小于 $3$。

先证充分性。若任意两点 $x$，$y$ 都同时包含在至少一个简单环中，则 $x$，$y$ 之间至少有两条不相交的路径。无论从图中删除哪个节点，$x$，$y$ 均能通过两条路径之一相连。故图中不存在割点，是点双连通图。

再证必要性。反证法，假设一张无向图是“点双连通图”，并且存在两点 $x$，$y$，他们不同时处于任何一个简单环中。

如果 $x$，$y$ 之间仅存在 $1$ 条简单路径，那么路径上至少有一个割点，与“点双连通”矛盾。

如果 $x$，$y$ 之间存在 $2$ 条或 $2$ 条以上的简单路径，那么容易发现，任意两条都至少有一个除 $x$，$y$ 之外的交点；进一步可推导出，$x$，$y$ 之间的所有路径必定同时交于除 $x$，$y$ 之外的某一点 $p$（不然就会存在两条没有交点的路径，形成一个简单环，如下图所示）。

![](https://cdn.luogu.com.cn/upload/image_hosting/o9pt519w.png)

根据定义，$p$ 是一个割点，与点双连通矛盾。故假设不成立。

证毕。

### 性质

1. 除了仅包含两个点一条边的点双外，其他点双都满足：任意两点间都存在至少两条点不重复路径。

1. 图中任意一个割点都在至少两个点双。

1. 两个点双至多存在一个公共点——割点。

1. 任意一个不是割点的点都只存在于一个点双中，割点也一定属于两个及以上的点双。

#### 证明

对于第一点，可以用点双连通分量的定义来解释：因为点双内无割点，所以两个点间一定会有多条边互通（否则就会存在割点）。

对于第二点，因为删去割点后图会不连通，所以割点至少连接着图的两部分，而由于点双中不能有割点，所以这两部分肯定不在同一个点双中，所以割点至少存在于两个点双中。

对于第三点，用反证法，假设存在两个及以上的公共点，那这两个点双就可以通过两条及以上的边相连，那么这就变成一个点双了，与定义矛盾，故假设不成立。如果这个公共点不是割点，那么说明两个点双还有别的边相连，同样变成一个点双，所以公共点一定是割点。

对于第四点，若点在两个及以上点双中，那么删去它就可以分成两个及以上的点双，它就一定是割点；而割点如果只属于一个点双，删去它后图依然连通，这个点就不是割点了，所以割点一定属于两个及以上的点双。
### 求法

点双连通分量是一个极其容易误解的概念。它与删除割点后图中剩余的连通块是不一样的，请格外留意。

若每个节点为孤立点，则它自己单独构成一个 v-DCC。除了孤立点之外，点双连通分量的大小至少为 $2$。根据 v-DCC 定义中的“极大”性，虽然桥（割边）不属于任何 e-DCC（边双连通分量），但是割点可能属于多个 v-DCC。下面的无向图共有 $2$ 个割点，$4$ 个点双连通分量。

![](https://cdn.luogu.com.cn/upload/image_hosting/0m1veoit.png)

我们考虑使用上面的 $dfn$ 和 $low$ 来求，我们将深度优先遍历时遇到的所有边加入到栈里面，当找到一个割点的时候，就将这个割点往下走到的所有边弹出，而这些边所连接的点就是一个点双了。

具体来说，需要在 Tarjan 算法的过程中维护一个栈，并按照如下方法维护栈中的元素：

1. 当一个节点**第一次**被访问时，把该节点入栈。

1. 当割点判定法则中的条件 $\mathit dfn_x\leq \mathit low_y$ 成立时，此时 $x$ 是割点，$subtree(y)$ 为一个点双连通分量。为了得到 $subtree(y)$，**无论** $x$ **是否为根**，都要将 $subtree(y)$ 弹出，具体操作如下：
	
    （1）栈顶为 $subtree(y)$ 的最底端（最深处），从栈中不断弹出节点，直至节点 $y$ 被弹出（$y$ **要弹出**）。
    
    （2）刚才弹出的所有节点**与节点** $x$ **一起**构成一个 v-DCC。

下面的程序在求出割点的同时，计算出 vector 数组 $dcc$，$\mathit dcc_i$ 保存编号为 $i$ 的 v-DCC 中的所有节点。

### 代码

```cpp 
#include <iostream>
#include <vector>
using namespace std;
const int N = 1000010, M = 5000010;
int head[N], ver[M * 2], Next[M * 2];
int dfn[N], low[N], stack[N];
int n, m, tot = 1, num, root, top, cnt;
vector<int> dcc[N * 2];//dcc[i] 存储编号为 i 的 v-DCC 中的所有节点
void add(int x, int y) {//邻接表存图
	ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}
void tarjan(int x) {
	dfn[x] = low[x] = ++num;
	stack[++top] = x;
	if (x == root && head[x] == 0) { //孤立点
		dcc[++cnt].push_back(x);
		return;
	}
	int flag = 0;
	for (int i = head[x]; i; i = Next[i]) {
		int y = ver[i];
		if (!dfn[y]) {
			tarjan(y);
			low[x] = min(low[x], low[y]);
			if (low[y] >= dfn[x]) {
				flag++;
				if (x != root || flag > 1)
					cut[x] = true;
				cnt++;
				int z;
				do {
					z = stack[top--];
					dcc[cnt].push_back(z);
				} while (z != y);
				dcc[cnt].push_back(x);
			}
		} 
		else
			low[x] = min(low[x], dfn[y]);
	}
}
int main() {
	ios::sync_with_stdio(false);//关闭与scanf的同步来提速
	cin >> n >> m;
	for (register int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		if (x == y)
			continue;
		add(x, y), add(y, x);
	}
	for (register int i = 1; i <= n; i++)
		if (!dfn[i])
			root = i, tarjan(i);
	cout << cnt << "\n";
	for (register int i = 1; i <= cnt; i++) { //输出
		cout << dcc[i].size();
		for (register int j = 0; j < dcc[i].size(); j++)
			cout << ' ' << dcc[i][j];
		cout << "\n";
	}
	return 0;
}
```
### 练习
[P8435 【模板】点双连通分量](https://www.luogu.com.cn/problem/P8435)。

[P8436 【模板】边双连通分量](https://www.luogu.com.cn/problem/P8436)。

注：本文大部分抄自 lyd 蓝书。

正在渲染内容...

P8435 【模板】点双连通分量 题解

P8435 【模板】点双连通分量题解