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 定义为以下节点的时间戳的最小值：

2. 通过 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。

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 割点

P3469 [POI2008]BLO-Blockade

点双连通分量

概念

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

无向图的极大点双联通子图被称为点双联通分量，简记为 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。

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

证明：

对于顶点数不超过 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. 除了仅包含两个点一条边的点双外，其他点双都满足：任意两点间都存在至少两条点不重复路径。

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

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

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

证明

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

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

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

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

求法

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

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

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

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

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

2. 当割点判定法则中的条件 \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 中的所有节点。

代码

#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 【模板】点双连通分量。

P8436 【模板】边双连通分量。

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