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$ 的第一次访问）构成一棵树。我们把它称为**无向连通图的搜索树**。当然，一般无向图（不一定连通）的各个连通块的搜索树构成无向图的搜索森林。 下图左侧展示了一张无向连通图，灰色节点是深度优先遍历的起点，加粗的边是发生递归的边（假设我们在遇到多个分支时，总是优先访问最靠左的一条）。右侧展示了深度优先遍历的搜索树，并标注了节点的时间戳。  #### 追溯值 除了时间戳之外， 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$。  #### 割点判定法则 若 $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$（不然就会存在两条没有交点的路径，形成一个简单环，如下图所示）。  根据定义，$p$ 是一个割点，与点双连通矛盾。故假设不成立。 证毕。 ### 性质 1. 除了仅包含两个点一条边的点双外，其他点双都满足：任意两点间都存在至少两条点不重复路径。 1. 图中任意一个割点都在至少两个点双。 1. 两个点双至多存在一个公共点——割点。 1. 任意一个不是割点的点都只存在于一个点双中，割点也一定属于两个及以上的点双。 #### 证明 对于第一点，可以用点双连通分量的定义来解释：因为点双内无割点，所以两个点间一定会有多条边互通（否则就会存在割点）。 对于第二点，因为删去割点后图会不连通，所以割点至少连接着图的两部分，而由于点双中不能有割点，所以这两部分肯定不在同一个点双中，所以割点至少存在于两个点双中。 对于第三点，用反证法，假设存在两个及以上的公共点，那这两个点双就可以通过两条及以上的边相连，那么这就变成一个点双了，与定义矛盾，故假设不成立。如果这个公共点不是割点，那么说明两个点双还有别的边相连，同样变成一个点双，所以公共点一定是割点。 对于第四点，若点在两个及以上点双中，那么删去它就可以分成两个及以上的点双，它就一定是割点；而割点如果只属于一个点双，删去它后图依然连通，这个点就不是割点了，所以割点一定属于两个及以上的点双。 ### 求法 点双连通分量是一个极其容易误解的概念。它与删除割点后图中剩余的连通块是不一样的，请格外留意。 若每个节点为孤立点，则它自己单独构成一个 v-DCC。除了孤立点之外，点双连通分量的大小至少为 $2$。根据 v-DCC 定义中的“极大”性，虽然桥（割边）不属于任何 e-DCC（边双连通分量），但是割点可能属于多个 v-DCC。下面的无向图共有 $2$ 个割点，$4$ 个点双连通分量。  我们考虑使用上面的 $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 蓝书。