小指针
2022/09/23阅读：63主题：凝夜紫
【图论专题】无向图的双连通分量的思路与应用
外部链接公众号无效，点击左下角“阅读原文”传送到我的博客获得更好的阅读体验。
前置知识
无向图的双连通分量实在实在太太太太难难难难了，如果有什么地方不懂可以先看完正篇文章（其实是先看看题目，结合代码注释这种笨方法理解），如果还是不会实属正常，毕竟这三道题可能过了今天我就写不出来了。
无向图的双连通分量问题
对于一个「无向图」，它有两种双连通分量：「边双连通分量（e-DCC）」和「点双连通分量（V-DCC）」。
「桥」：如果在一个无向图内，删除一条边会使图变得不连通，则称这条边为“桥”。（难道是象征着独木桥？）
> 「边的双联通分量」：最大的，不含有「桥」的联通区域，称为“边的双联通分量”。因此，我们就能推出两个性质：
「在边双联通分量中，不管删除哪条边，整个区域依旧是联通的」。 「在边双联通分量中的任意两个点之间，一定包含两条不想交的路径」。 「割点」：如果一个无向图内，删掉一个点会使图变得不连通，则称这个点为“割点”。
「点的双联通分量」：最大的，不包含「割点」的区域，称为“点的双联通分量”。由此，我们也能推出相关性质：
每个割点至少属于两个点双联通分量。
Tarjan 算法求边的双连通分量
与求有向图的强连通分量一样，也需要 dfn 数组和 low 数组，且「含义相同」。
dfn[u]数组：给 DFS 序遍历，经过的每个点一个编号，我们称这个编号为时间戳。low[u]数组：以u为根的子树向下遍历，所能到达的「最早的点」（时间戳编号最小的点）。
在求边的双连通分量中，我们可以分步解决：
-
「如何判断某条边是桥」？
假设，当前点为
x，它通过当前边走到了另一个点y，那么我们只需要看一下，点y是否可以到达x或者x的祖先节点（除了当前边），即可判断出当前边是不是「桥」。在实现上，等价于
dfn[x] < low[y]，也就是说：「x 可以到 y，但是 y 能到的时间戳编号最小的点就是自己，而无法到达 x 的编号。」 -
「如何找到边的双连通分量」？
-
一种比较简单的做法是：
将所有的桥删掉，那么根据定义剩下的连通块就一定是边的双连通分量。 -
另一种方式，类似找有向边的强连通分量，使用「栈」结构：「把从点 u 开始遍历到的点加入到栈，搜索到分支结束之后，发现有
dfn[x]==low[x]，说明 走不到点 x 的上面（因为 low 的含义是从 x 出发能走到最下的点，而 x 上面的点一定比 x 更小），那么当前分支里面 还在栈中的节点 就是当前边的双连通分量中的点」。
-
Tarjan 算法求边的双连通分量
与求有向图的强连通分量一样，也需要 dfn 数组和 low 数组，且「含义相同」。
dfn[u]数组：给 DFS 序遍历，经过的每个点一个编号，我们称这个编号为时间戳。low[u]数组：以u为根的子树向下遍历，所能到达的「最早的点」（时间戳编号最小的点）。
在求点的双连通分量中，我们可以分步解决：
-
「如何判断某个点是不是割点」？
假设，当前搜到了点
x，由x走到了y，如果low[y]>=dfn[x]：-
如果
x不是根节点，那么去掉x，y就没办法连通到x上，因为最小的y也大于等于x的编号。所以x就是一个割点。 -
如果
x是根节点，那么它至少要有两个子节点，x 才是割点。如下图，当没有子节点Z的时候，我们发现把节点X删掉，依旧不影响剩下的区域连通。也就是还要有low[z]>=dfn[x]。
-
-
「如何找到点的双连通分量」？
同样使用使用「栈」结构来存储数据。我们从当前点
x往下搜，搜到了y，那么如果存在dfn[x] <= low[y]，说明从y出发能搜到的最小点就是x，而不可能搜到x的上面，我们累积类似这种子树的数量，假如这种子树的数量大于一或者说x不是根节点，那么说明我们「找到了一个割点」。如果x是割点，那么我们把栈中的元素弹出，直到弹出y位置。（注意是弹出y位置，而不是弹出x位置，因为tarjan同学规定割点x也属于该点的双连通分量中。）
AcWing 395. 冗余路径
为了从 F 个草场中的一个走到另一个，奶牛们有时不得不路过一些她们讨厌的可怕的树。
奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择。
每对草场之间已经有至少一条路径。
给出所有 R 条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量，路径由若干道路首尾相连而成。
两条路径相互分离，是指两条路径没有一条重合的道路。
但是，两条分离的路径上可以有一些相同的草场。
对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路。
「输入格式」
第 1 行输入 F 和 R。接下来 R 行，每行输入两个整数，表示两个草场，它们之间有一条道路。
「输出格式」
输出一个整数，表示最少的需要新建的道路数。「数据范围」
1≤F≤5000, F−1≤R≤10000「输入样例」
7 7 1 2 2 3 3 4 2 5 4 5 5 6 5 7「输出样例」
2
题目描述
有 F 个点，奶牛们希望每一对点之间有两条互相分离的路径，每对点之间至少已经有了一条路径。给出 R 个双向边，问达成奶牛们的目标需要「最少」新建多少个边。（「互相分离的路径」指的是一对点之间不同的两条边。）
题目分析
首先比较明显的是，奶牛们的愿望符合我们对「边的双连通分量」的定义。
边的双连通分量：没有桥的无向连通图。没有桥，也就是不存在两点之间只有一条边的情况，进一步的，就是说明无向连通图中，每两点之间至少有两条边，且两条边不相交，不重合。
所以，本题就转换成了「至少增加多少个点，可以使整个图变成边的双连通分量」。
这样的话，我们的思路就比较明确了：
-
「对于给出的无向连通图，可能存在很多 边的双连通分量，那么根据边的双连通分量的定义，这些分量中一定已经不存在桥了。所以，我们把这些边的双联通分量都找出来，然后缩成一个点（缩点），这样缩点后的图中 两两之间的点一定都是一条边的（也就是由桥连接的），因为我们已经把不是桥的分量都缩成一个点了。」。
-
「缩点后，因为全部都是由桥进行连接的，所以整个无向图会变成一棵树或者森林，而我们想让树或者森林变成 边的双连通分量，只需要在所有出度为 0 的叶子结点数量的一半连接上就行了」。
如上图所示，我们把「叶子节点 两两相连接」后，如果还有一个节点剩余，就把「剩余的那个节点随便连一条边」，所以，总共就是「叶子节点的数量除以 2，向上取整，既，5/3=3」。
Code
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5010, M = 20010;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int id[N], dcc_cnt;
bool is_bridge[N];
int d[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 因为是无向边，所以必须记录当前边的前驱边 避免往回搜
void tarjan(int u, int from) {
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j, i);
low[u] = min(low[u], low[j]);
// 与有向图强连通分量不同的地方：搜完之后 判断 j能否到u
if (dfn[u] < low[j])
// 正向边 反向边都是桥 i^1是反向边的编号
is_bridge[i] = is_bridge[i ^ 1] = true;
// 与有向图强连通分量不同的地方2：确保当前的无向边不是父节点过来的
// 因为我们不能用前驱节点的时间戳 去更新 当前节点的时间戳
} else if (i != (from ^ 1))
low[u] = min(dfn[u], low[j]);
}
if (dfn[u] == low[u]) {
++ dcc_cnt;
int y;
do {
y = stk[ top --];
id[y] = dcc_cnt;
} while (y != u);
}
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- ) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
tarjan(1, -1);
for (int i = 0; i < idx; i ++ ) {
//如果边i是桥 在其所连的出边 的点j 所在的 双连通分量的度+1
// 桥两边的双连通分量各+1
if (is_bridge[i]) {
d[id[e[i]]] ++ ;
}
}
int cnt = 0;
for (int i = 1; i <= dcc_cnt; i ++ ) {
if (d[i] == 1) cnt ++ ;
}
printf("%d\n", (cnt + 1) / 2);
return 0;
}
AcWing 1183. 电力
给定一个由 n 个点 m 条边构成的无向图，请你求出该图删除一个点之后，连通块最多有多少。
「输入格式」
输入包含多组数据。每组数据第一行包含两个整数 n,m。
接下来 m 行，每行包含两个整数 a,b，表示 a,b 两点之间有边连接。
数据保证无重边。
点的编号从 0 到 n−1。
读入以一行 0 0 结束。
「输出格式」
每组数据输出一个结果，占一行，表示连通块的最大数量。「数据范围」
1≤n≤10000, 0≤m≤15000, 0≤a,b < n「输入样例」
3 3 0 1 0 2 2 1 4 2 0 1 2 3 3 1 1 0 0 0「输出样例」
1 2 2
题目描述
给出一个 n 个点, m 条边的无向图，问我们删除一个点后，剩下的连通块数量最多有多少。
题目分析
从题目的问题来看，本题目标是求「删除一个点后，联通块的最大数量」，那么根据我们上面对「割点」的定义，可以发现删掉的这个点，如果不是割点，则对总的联通块数量没有影响；如果删掉的这个点是割点，则当前点下面的所有区域，都是新增加的联通区域，特别的，如果该割点不是根节点，那么该割点的前驱区域也要算作新增区域。最后，所有新增区域的数量减一，表示去掉一个原联通块。
基于上述分析，我们可以制定如下算法：
-
统计出所有联通块的数量，维护一个最大的增加联通块数量；
-
遍历每个联通块，遍历联通块中的每一个点，判断删掉这个点之后可能增加的联通块数量，更新最大的增加联通块数量。
-
最后，「所有的原联通块数量加上最大新增联通块数量」就是答案。
Code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010, M = 30010;
int h[N], e[M], ne[M], idx;
int stk[N], top;
int dfn[N], low[N], timestamp;
int n, m;
int root, ans; // root 根节点 ans 存储最大新增节点数量
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void tarjan(int u) {
dfn[u] = low[u] = ++ timestamp;
int cnt = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j);
low[u] = min(low[u], low[j]);
// j无法走到u的上面 说明u是割点
if (low[j] >= dfn[u]) cnt ++ ;
} else low[u] = min(low[u], dfn[j]);
}
// 如果u不是当前分支的根节点 则根节点上面的联通区域也要计算到
if (u != root) cnt ++ ;
ans = max(ans, cnt);
}
int main() {
while (cin >> n >> m, n || m) {
memset(h, -1, sizeof h);
memset(dfn, 0, sizeof dfn);
idx = timestamp = 0;
while (m -- ) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
ans = 0;
int cnt = 0; // 统计所有原联通块的数量
// 注意本题节点的编号 从0开始 到n-1 而不是常规的1~n
for (root = 0; root < n; root ++ ) {
if (!dfn[root]) {
cnt ++ ;
tarjan(root);
}
}
printf("%d\n", ans + cnt - 1);
}
return 0;
}
AcWing 396. 矿场搭建
煤矿工地可以看成是由隧道连接挖煤点组成的无向图。
为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。
于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。
请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。
「输入格式」
输入文件有若干组数据，每组数据的第一行是一个正整数 N，表示工地的隧道数。接下来的 N 行每行是用空格隔开的两个整数 S 和 T，表示挖煤点 S 与挖煤点 T 由隧道直接连接。
注意，每组数据的挖煤点的编号为 1∼Max，其中 Max 表示由隧道连接的挖煤点中，编号最大的挖煤点的编号，可能存在没有被隧道连接的挖煤点。
输入数据以 0 结尾。
「输出格式」
每组数据输出结果占一行。其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与 : 之间无空格，: 之后有空格）。
其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总数。
输入数据保证答案小于 2^64，输出格式参照以下输入输出样例。
「数据范围」
1≤N≤500， 1≤Max≤1000「输入样例」
9 1 3 4 1 3 5 1 2 2 6 1 5 6 3 1 6 3 2 6 1 2 1 3 2 4 2 5 3 6 3 7 0「输出样例」
Case 1: 2 4 Case 2: 4 1
题目描述
给出一个无向图，表示矿场，现在需要设置一些出口，问题是 「最少在几个点设置出口」，可以使不管其他哪个点坍塌（被删掉），其余所有点都可以与某个出口联通。
题目分析
首先要明确的第一点是「设置的出口个数至少至少需要两个」，因为只设置一个出口的话，这个出口坍塌，直接就GG了。
然后，我们可以单独的去看每一个连通块，分情况讨论：
-
点的双连通分量中，「没有任何割点」，这意味着无论删掉哪个出口，整个图都仍然是连通的，并且因为至少两个出口，那么总共的选择方案就是 ，表示的意思是「从cnt个总点数中选出来两个」。
-
点的双连通分量中「存在割点」，此时，我们就需要缩点了。而点的双连通分量的缩点与
有向图强连通分量 和 边的双连通分量有所不同，因为一个割点，可能属于多个点的双连通分量，如下图所示。
因此，缩点的时候，我们也要「把割点算在点的双连通分量中，每个割点单独算作一个点，从V-DCC向其每个所包含的每个割点连一条边」，如下图所示。
-
到此为止，我们发现如果割点是出口，那么坍塌的那个出口是割点的话，如果「这个割点两面的点，只有该割点一个出口（也就是它们的度为1），那么该割点坍塌，它俩就无法跑到别的连通分量中，因此只能自救，在他们内部设置一个出口」。如下图所示。
-
如果「联通分量缩成的点度数大于1」，那么即便坍塌一个割点，他们依旧可以通过另外的割点逃跑。
Code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef unsigned long long ULL; // 答案最大可以到2^64
const int N = 1010, M = 1010;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int dcc_cnt;
vector<int> dcc[N]; // 存储连通分量中的每个点
bool cut[N]; // 判断每个点是否是割点
int root;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void tarjan(int u) {
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u;
// 特判u是孤立点的情况 u自己也算作一个连通分量
if (u == root and h[u] == -1) {
dcc_cnt ++ ;
dcc[dcc_cnt].push_back(u);
return ;
}
int cnt = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j);
low[u] = min(low[u], low[j]);
if (dfn[u] <= low[j]) {
cnt ++ ;
// 判断u是否割点 如果不是根节点-只要有一个分支他就是割点 或者 如果是根节点 需要有两个分支才是割点
// root /
// / \ 非root(自带上面一个边,所以只要一个下分支)
// /
if (u != root or cnt > 1) cut[u] = true;
++ dcc_cnt;
int y;
do {
y = stk[top -- ];
dcc[dcc_cnt].push_back(y);
} while (y != j); // 注意这里要一直弹出到j（也就是分析里面的y）
dcc[dcc_cnt].push_back(u);
}
} else low[u] = min(low[u], dfn[j]);
}
}
int main() {
int T = 1; // 多组数据
while (cin >> m, m) {
// 因为没写这句 调了两个小时 这句是为了清空所有的dcc中的点
for (int i = 1; i <= dcc_cnt; i ++ ) dcc[i].clear();
idx = n = timestamp = top = dcc_cnt = 0;
memset(h, -1, sizeof h);
memset(dfn, 0, sizeof dfn);
memset(cut, 0, sizeof cut);
while (m -- ) {
int a, b;
cin >> a >> b;
n = max(n, a), n = max(n, b); // 更新出最大的挖煤点编号
add(a, b), add(b, a);
}
for (root = 1; root <= n; root ++ ) {
if (!dfn[root]) tarjan(root);
}
int res = 0; // 统计最少需要的出口数量
ULL num = 1; // 统计设置出口的方案数
for (int i = 1; i <= dcc_cnt; i ++ ) {
// 统计第i个连通块内有多少个割点。
// 分析中我们说明了割点要算在连通块内.
int cnt = 0;
for (int j = 0; j < dcc[i].size(); j ++ ) {
// 第i个联通分量中的第j个点是割点
if (cut[dcc[i][j]]) cnt ++ ;
}
// 没有割点的情况
if (cnt == 0) {
if (dcc[i].size() > 1) res += 2, num *= dcc[i].size() * (dcc[i].size() - 1) / 2;
else res ++ ;
}
// 连通分量只有一个割点 则至少需要的割点数量++
// 增加的这个割点 在这个连通分量的任意点上
else if (cnt == 1) res ++ , num *= dcc[i].size() - 1;
}
printf("Case %d: %d %llu\n", T ++ ,res, num);
}
return 0;
}
「END」
作者介绍