Tarjan求无向图割边
——YMO《Behind The Mask》
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$,我们只需考虑这样的点:
- 存在非搜索树上的边$(u,v)$的$v$点
- 在回溯前能访问到的最早的点,即搜索树中以$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的代码块样式好看!