双连通分量、割点与桥

双连通分量

双连通分量Double Connected Components，简称 （电磁场）。是连通分量在无向图中的体现。分为点双连通分量 和边双连通分量 。在一张连通无向图中，任意删去一条边，如果无论如何都不能使点 不连通，那么就称 边双连通；同样在一张连通无向图中，任意删去一个点（ 除外），如果无论如何都不能使 不连通，则称 点双连通。

反之，如果这个无向连通图中不满足上述的定义，那么使它不满足定义删去的那条边/点就叫做原图的桥/割点。换句话说， 就是不含桥的极大无向连通图； 是不含割点的极大无向连通图。

双连通分量求解流程

其实和求强连通分量的代码逻辑很相似。但是不同的一点是，无向 图中不存在“横叉边”这一说。因此循环判断里 else if (in_stk[j]) 就出错了，此时我们只需判断当前的边是否是一条原路返回的边，如果不是的话再用 dfn[j] 更新 low[u]。

对于当前遍历到的边，它是一个桥，当且仅当下边的点 无法走回 ，因为在 中，是不允许回到上边的点的（防死循环）。形式上说，就是 dfn[u] < low[j]。

另外，代码中下标涉及到的位运算需要建立在建图下标从 开始的基础上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include <bits/stdc++.h>
#define N 5010
#define M 10010
using namespace std;

struct Edge {
    int to, ne;
} edges[M << 1];
int h[N], idx = 0;
int dcc_cnt = 0, dfs_cnt = 0;
int dcc_id[N];
int dfn[N], low[N];
stack<int> stk;
int indeg[N];
bool is_bridge[M];

void add(int a, int b) {
    edges[idx].to = b;
    edges[idx].ne = h[a];
    h[a] = idx++;
}

void tarjan(int u, int f) {
    dfn[u] = low[u] = ++dfs_cnt;
    stk.push(u);
    for (int i = h[u]; ~i; i = edges[i].ne) {
        int j = edges[i].to;
        if (!dfn[j]) {
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if (dfn[u] < low[j]) {
                is_bridge[i] = is_bridge[i ^ 1] = true;
            }
        } else if (i != (f ^ 1)) {
            low[u] = min(low[u], dfn[j]);
        }
    }
    if (dfn[u] == low[u]) {
        dcc_cnt++;
        int t;
        do {
            t = stk.top();
            stk.pop();
            dcc_id[t] = dcc_cnt;
        } while (t != u);
    }
}

割点求解流程

如果某个点是割点，那么剩下的还未访问过的点至少会有一个在不经过它的情况下永远无法到达任何已经遍历过的点。形式化讲就是 low[y] >= dfn[x]，对于当前遍历到的的节点，存在两种情况：

1. 为根节点，必须有至少两个树枝
2. 不为根节点，当前就是割点

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void tarjan(int u) {
    dfn[u] = low[u] = ++dfs_cnt;
    stk.push(u);
    int deg = 0;
    for (int i = h[u]; ~i; i = edges[i].ne) {
        int j = edges[i].to;
        if (!dfn[j]) {
            deg++;
            tarjan(j);
            low[u] = min(low[u], low[j]);
            if ((j != root && dfn[u] <= low[j]) || (j == root && deg)) cut[u] = true;
        } else low[u] = min(low[u], dfn[j]);
    }
}

典例

洛谷 P2860 [USACO06JAN] Redundant Paths G

题目地址：P2860

题目难度：提高+/省选-

为了从 个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树．奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择。

每对草场之间已经有至少一条路径．给出所有 条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量，路径由若干道路首尾相连而成．两条路径相互分离，是指两条路径没有一条重合的道路．但是，两条分离的路径上可以有一些相同的草场．对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路。

输入格式：

第一行为两个整数 和 。

接下来 行，每行两个整数，代表每条道路所连接的两个草场的编号。

输出格式：

仅一行，最少需要兴修的道路的数量。

这道题和校园网的子任务 相对，都是把一个图补充成对应分量所需添加的边数，因此可以类比。这道题的结论是，补充 条边可以使得原图成为一个 ，其中 为搜索树中叶子节点的个数。

感性理解，因为每个合法 中的每两个点之间都有至少两条不相同的路径可以互相到达。发现如果删去叶子节点上边的那条边，整张图一定是分离的，因此我们就需要把叶子节点的边补齐。考虑在叶子节点之间互相连边，答案是 。

叶子节点的判断——在缩点后对入度为 的节点。

代码在此

AcWing 1183 电力

题目地址：AcWing 1183

题目难度：中等

给定一个由 个点 条边构成的无向图，请你求出该图删除一个点之后，连通块最多有多少。

输入格式：

输入包含多组数据。

每组数据第一行包含两个整数 。

接下来 行，每行包含两个整数 ，表示 两点之间有边连接。

数据保证无重边。

点的编号从 到 。

读入以一行 结束。

输出格式：

每组数据输出一个结果，占一行，表示连通块的最大数量。

数据范围：

首先维护出原先图中的连通块个数，然后我们再考虑删除哪个连通块里的哪个点，对于每个连通块。它可能存在割点，在删除割点后，整个连通块会裂成小块，而块的个数就是这个割点的度数。因此假设我们从 个连通块中选择了连通块 内的某个点 ，答案就是 。

因此在 找割点时统计维护割点度数的最大值即可。

代码在此

P3225 [HNOI2012] 矿场搭建

题目地址：P3225

题目难度：省选/NOI-

题目来源：湖南  2012

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

输入格式：

输入文件有若干组数据。

每组数据的第一行是一个正整数 ，表示工地的隧道数。

接下来的 行每行是用空格隔开的两个整数 和 ，表示挖煤点 与挖煤点 由隧道直接连接。

输入数据以 结尾。

输出格式：

对于每组数据，输出一行。

第 行组数据以 开始（注意大小写， 与 之间有空格， 与 之间无空格， 之后有空格）。

其后是用空格隔开的两个正整数，第一个正整数表示对于第 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 组输入数据不同最少救援出口的设置方案总数。

输入数据保证答案小于 。输出格式参照以下输入输出样例。

数据范围：

对于每组数据，设 为各组 中最大值，有：

• ；
• 各组 构成的集合 。
• 中任意两点连通。

考虑把几种情况分类归纳。首先，因为保证每一个每个点都能走到出口，因此全局出口数一定是大于等于 的，极端情况就是把出口设置在某点，然后这个点坍塌了，最好情况下剩余的节点都可以从第二个出个出去。

然后就是每个连通块内必须有出口，如果这个连通块里不存在割点，是一个 ，显然无论哪个点坍塌，都不影响全图的连通性。剩下就是上边所说的出口数必须大于等于 的问题。任意放置两个出口，因此总方案数为 ；反之，如果出现割点——如果坍塌的是割点，等价于把割点连接的若干连通块分开，每一个新连通块都是一个 ，内部点可以互相到达。考虑到题面所说只会坍塌一个点，因此无需担心被分开的 中有点坍塌的情况，因此可以在连通块内任意设置出口，方案数为该连通块的大小；如果坍塌的是某个连通块内部的点，这若干连通块仍然可以经过割点，因此在割点设置出口。

根据乘法原理，答案需要相乘得出。数据范围是 ，因此要用 unsigned long long。（long long 最大到 ）。

代码在此