Tarjan求无向图割边

Tarjan算法

不得不说Robert Tarjan真的是大师，发个网站大家感受一下——论文索引。

这里要说的Tarjan算法用于解决无向图的连通性，学习之前，先了解两个概念。

无向连通图的搜索树

当我们遍历一个无向连通图时，显然一个点只会被访问一次，而访问一个点的方法是从一个当前已访问的点$u$，沿着它的邻边走向未访问过的点$v$，则对于任意非遍历起点，其都唯一对应一条边$(u,v)$，这些边恰巧构成一棵树（深究其证明，可考虑将$(u,v)$视为有向边，则非起点入度为$1$，起点入度为$0$），我们称之为无向连通图的搜索树。

由于DFS序不唯一，所以搜索树也不唯一。若按节点编号顺序遍历图，则搜索树如下图中加粗部分：

graph LR
A((A))
B((B))
C((C))
D((D))
E((E))
A === B
A --- C
B === C
B --- D
C === D
C === E

时间戳dfn

按照DFS的先后顺序，我们可以为每个节点定义一个访问时间，其为该点在DFS序中的下标，我们称之为时间戳。对于上图，DFS序为$ABCDE$，则若从$1$开始标记时间，则各点时间戳为：

graph LR
A((1))
B((2))
C((3))
D((4))
E((5))
A === B
A --- C
B === C
B --- D
C === D
C === E

追溯值low

当DFS序不同时，我们对节点标记的$dfn$也不尽相同，例如上图稍加改变，即可得到：

graph LR
A((1))
B((2))
C((4))
D((3))
E((5))
A === B
A --- C
B --- C
B === D
C === D
C === E

所以单纯考虑dfn似乎没什么意义。

我们考虑这样一个事实：若一个点$u$存在非搜索树上的邻边$(u,v)$，且$dfn(u)>dfn(v)$，则显然遍历到点$v$（先于$u$）时，如果我们先走$(u,v)$，那么$dfn(u)$将减小为$dfn(v)+1$。

更准确地说，若一个点$u$存在不在搜索树上的邻边$(u,v)$，则必然有$dfn(u)>dfn(v)$，读者可以思考下为什么。

那么，对任一点而言，我们将所有可优化的边枚举出来，则其中存在一个最小的优化值，但这个值是我们可以优化到的最小时间戳吗？并非如此，我们对上图稍作改动：

graph LR
A((1))
B((3))
C((5))
D((4))
E((6))
F((2))
A === F
F === B
A --- E
B --- C
B === D
C === D
C === E

可以发现，当我们DFS到$6$时，我们有非搜索树上的邻边指向$1$，则$6$的$dfn$事实上可以被优化为$2$，当回溯到$5$时，我们发现$5$有非搜索树上的邻边指向$3$，则$5$的$dfn$可被优化为$4$。但由于我们是从$6$开始回溯的，既然$6$能被优化为$2$，那么$5$肯定能被优化到$3$。

但这样还是无法避免因为DFS序不同产生的不唯一性问题，不过上述思考给我们指明了一个方向——我们不妨试着找到任意点能回溯到的最早的点的时间戳。与上面过程类似，对于任意点$u$，我们只需考虑这样的点：

1. 存在非搜索树上的边$(u,v)$的$v$点
2. 在回溯前能访问到的最早的点，即搜索树中以$u$为根的子树上的点能访问到的最早的点

找出这些点中的最小的时间戳，即为我们能追溯到的最早节点，我们称之为追溯值$low$。则依上述定义，我们可求得上图追溯值（A/B表示时间戳为A，追溯值为B）：

graph LR
A((1/1))
B((3/1))
C((5/1))
D((4/1))
E((6/1))
F((2/1))
A === F
F === B
A --- E
B --- C
B === D
C === D
C === E

我们发现上图各点都能追溯到$1$，若变换下例子：

graph TB
1((1/1))
2((2/1))
3((3/1))
4((4/1))
5((5/1))
6((6/6))
7((7/7))
8((8/6))
9((9/6))
1 === 2
2 === 3
3 === 4
4 === 5
2 --- 5
1 --- 5
1 -.- 6
6 -.- 7
6 === 8
6 --- 9
8 === 9

无向图的割边及判定

对于无向连通图$G(V,E)$，若删去边$e\in E$后，$G$被分为两个不连通的子图，则称$e$为割边或桥。

根据上面$dfn$和$low$，很容易能想出割边的方法——无向边$(u,v)$是割边，当且仅当搜索树上存在$u$的一个子节点$v$，满足：

$$dfn[u]<low[v]$$

如果不明白上式，可以想象，$dfn[u]$指代了一条从起点到$u$的搜索树链，而$low[v]$代表了一条从$v$到$low[v]$对应的点的回溯链。那么若$dfn[u]<low[v]$，则这两条链相连状似一条穿起来的皮带（加粗部分），那么删掉皮带多出来的那一截中的任意一条边，都能使将原图分为两个不连通的子图（后面的点都无法追溯到$u$）：

graph LR
s((s))
a((a))
b((b))
u((u))
v((v))
s --- u
u === v
v === a
a === b
b === v

若$dfn[u]=low[v]$，则状似闭环：

graph LR
s((s))
a((a))
u((u))
v((v))
s --- u
u === v
v === a
a === u

若$dfn[u]>low[v]$，则状似未穿起的皮带：

graph LR
s((s))
a((a))
b((b))
u((u))
v((v))
s --- u
u === v
v === a
a === b
b === s

是不是形象了很多？当然，这只是个辅助记忆的可爱的例子，因为如果从递归的最远的节点开始，存在无非搜索树上邻边的点，则上图两条链应当在某些部分重合。但在割边附近，都能形成状似上面三种情况的图形，单链除外：

graph LR
s((s))
u((u))
a((a))
b((b))
v((v))
t((t))
s --- u
u --- a
a --- b
b --- v
v --- t

上图中显然任意一条边都为割边。

对重边的处理

显然，当图中存在重边时，我们上面的$low$值求法存在问题，若仅考虑符合条件的两种点，即使存在重边，求得的$low$也不会变化，然而显然下图并不存在割边：

graph LR
A((A))
B((B))
C((C))
D((D))
A --- B
A --- B
B --- C
C --- D
D --- B

若不做一些处理，则会得到存在割边$(A,B)$的错误答案。

一个可行的方法是——每个点的访问情况仅用于控制不重复遍历点，更新$low$值时转而考虑每条边是否访问过，如果存在未访问过的非搜索树上的边，更新其$low$即可。

这里有必要对每条边做标记处理吗？显然不用。

由于我们搜索时形成的是一棵树，那么我们在从节点$u$搜得邻点$v$时，纵使$(u,v)$可能不唯一，但真正访问的$(u,v)$有且仅有一条，当我们回溯时，仅需避开这条边的反向边（^1）即可。因此，我们可以在DFS函数中加一参数，用于记录走到当前节点来时的边的编号。

参考实现

//
// Created by Visors on 2020/10/27.
//
// 题目名：T103481 【模板】割边
// 题目来源：luogu
// 题目链接：https://www.luogu.com.cn/problem/T103481
// 算法：Tarjan
// 用途：无向图割边
// 时间复杂度：O(n+m)
//

#include <bits/stdc++.h>

using namespace std;

struct Tarjan {
    struct Edge {
        int to, next;

        Edge() = default;

        Edge(int to, int next) : to(to), next(next) {}
    };

    int vertexNum{}, edgeNum{};
    int cnt{};                // 当前时间戳
    vector<Edge> edges;
    vector<int> heads;
    vector<int> dfn;        // 时间戳
    vector<int> low;        // 最早追溯时间
    vector<int> bridges;     // 桥边编号集

    void init(int n, int m) {
        cnt = 0;
        vertexNum = n;
        edgeNum = m;
        heads.resize(vertexNum);
        fill(heads.begin(), heads.end(), -1);
        dfn.resize(vertexNum);
        low.resize(vertexNum);
        bridges.clear();
    }

    void addEdge(int u, int v) {
        edges.emplace_back(v, heads[u]);
        heads[u] = edges.size() - 1;
    }

    void dfs(int u, int inEdge) {
        dfn[u] = low[u] = ++cnt;
        for (int i = heads[u]; ~i; i = edges[i].next) {
            int &v = edges[i].to;
            if (!dfn[v]) {
                dfs(v, i);
                low[u] = min(low[u], low[v]);
                if (low[v] > dfn[u]) bridges.push_back(i);
            } else if (i != (inEdge ^ 1))
                low[u] = min(low[u], dfn[v]);
        }
    }

    void run() {
        for (int i = 0; i < vertexNum; i++)
            if (!dfn[i]) dfs(i, -1);
    }
} tarjan;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    tarjan.init(n, m);
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        u--, v--;
        tarjan.addEdge(u, v);
        tarjan.addEdge(v, u);
    }
    tarjan.run();
    cout << tarjan.bridges.size() << endl;
//    for (int it:tarjan.bridges)
//        cout << tarjan.edges[it ^ 1].to << ' ' << tarjan.edges[it].to << endl;
    return 0;
}

还是觉得Wowchemy的代码块样式好看！