连通性问题
SkyDreamer
·
·
算法·理论
强连通分量
定义
强连通的定义是：有向图 G 强连通是指，G 中任意两个结点连通。
强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图。
Tarjan 算法
DFS 生成树
在介绍该算法之前，先来了解 DFS 生成树，我们以下面的有向图为例：
有向图的 DFS 生成树主要有 4 种边（不一定全部出现）：
- 树边（tree edge）：示意图中以黑色边表示，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
- 反祖边（back edge）：示意图中以红色边表示（即 7 至 1），也被叫做回边，即指向祖先结点的边。
- 横叉边（cross edge）：示意图中以蓝色边表示（即 9 至 7），它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点 并不是 当前结点的祖先。注意:起点的 dfn 大于终点的 dfn。
-
前向边（forward edge）：示意图中以绿色边表示（即 3 至 6），它是在搜索的时候遇到子树中的结点的时候形成的。
我们考虑 DFS 生成树与强连通分量之间的关系。
如果结点 u 是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 u 为根的子树中。结点 u 被称为这个强连通分量的根。
Tarjan 算法求强连通分量
在 $Tarjan$ 算法中为每个结点 $u$ 维护了以下几个变量：
>$dfn_u$ : $u$ 的 $dfs$ 序。
>
>$low_u$ : 在 $u$ 的子树中能够回溯到的最早的已经在栈中的结点。设以 u 为根的子树为 ${Subtree}_u$。${low}_u$ 定义为以下结点的 $dfn$ 的最小值：$Subtree_u$ 中的结点；从 $Subtree_u$ 通过一条不在搜索树上的边能到达的结点。不过可淡化其意义，变成辅助合并的标志。
显而易见，一个结点的子树内结点的 $dfn$ 都大于该结点的 $dfn$。
从根开始的一条路径上的 $dfn$ 严格递增，$low$ 严格非降。
---
按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索，维护每个结点的 $dfn$ 与 $low$ 变量，且让搜索到的结点入栈。每当找到一个强连通元素，就按照该元素包含结点数目让栈中元素出栈。在搜索过程中，对于结点 $u$ 和与其相邻的结点 $v$（$v$ 不是 $u$ 的父节点）考虑 $3$ 种情况：
1. $v$ 未被访问：继续对 $v$ 进行深度搜索。在回溯过程中，用 $low_v$ 更新 $low_u$。因为存在从 $u$ 到 $v$ 的直接路径，所以 $v$ 能够回溯到的已经在栈中的结点，$u$ 也一定能够回溯到。
2. $v$ 被访问过，已经在栈中：根据 $low$ 值的定义，用 $dfn_v$ 更新 $low_u$。
3. $v$ 被访问过，已不在栈中：说明 $v$ 已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。
---
### Code
```
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define N 10005
using namespace std;
int n,m;
vector<int> e[N];
int dfn[N],low[N],cnt;//节点信息
int st[N],top;//栈
bool ins[N];//是否在栈中
int idx,sz[N],bel[N];//sz = size , bel = belong ,字面意思 , 统计答案
int ans;
inline void dfs(int u){
dfn[u]=low[u]=++cnt;//维护 dfn 和 low
ins[st[++top]=u]=true;//维护栈和栈标记，学会适当压行，增加代码可读性
for(int i=0;i<e[u].size();i++){
int v=e[u][i];//枚举
if(!dfn[v]){//没访问过
dfs(v);//访问
low[u]=min(low[u],low[v]);//回溯后用 dfn[v] 更新 dfn[u]
}else if(ins[v]){//访问过，在栈中，说明 v 属于一个未处理完的强连通分量
//一石二鸟，包含返祖边和前向边的更新
//返祖边: 更新为返祖边的 dfn 序
//前向边: 前向边的 dfn 序定大于 dfn[u] , 无影响，即为废物
low[u]=min(low[u],dfn[v]);
}
//横叉边:无需考虑, 原因: 若不在栈中，已被取出，在其他强连通分量中，若在栈中，已被上方 if 语句考虑了 ，无影响。
}
if(dfn[u]==low[u]){//若相等，找到一组强连通分量
int v; ++idx;//序号加一
do{
v=st[top--];//取出
ins[v]=false;//出栈的标记
bel[v]=idx;//所属强连通分量序号
++sz[idx];//大小加一
}while(v!=u);//取到自己出去为止
//do_while 真神奇,n 年没用了, 除了刚学打了几次模板，有发挥作用了
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v; scanf("%d%d",&u,&v);
e[u].push_back(v);
}//输入, 建边
for(int i=1;i<=n;i++){
if(!dfn[i]) dfs(i);
}//一次 dfs 不一定遍历所有点，要跑多次
for(int i=1;i<=idx;i++) ans+=(sz[i]>1);
printf("%d",ans);//题目要求
for(int i=1;i<=n;i++){
printf("%d%c",bel[i],"\n"[i==n]);
}//输出每个节点的对应强连通分量编号
return 0;//56 行华丽结束
}
```
时间复杂度: $O(n+m)$。
### 拓扑排序
考察 $Tarjan$ 中被最优先处理的是什么样的点，发现显然就是那些没有出度的点，而这和拓扑排序反全是反过来的。而又因为我们的 $SCC$ 编号是按顺序排的，所以本质上相当于把拓扑序反了过来。
**因此，SCC 编号等于逆拓扑序。**
**但DP 转移顺序应为拓扑序**
### 一些结论
一个有向图中，如果将所有强连通分量缩成一个点，则这个图一定无环。即为 $DAG$ 图。
### 证明
反证，假设这个图中有环，环上的点代表的 $SCC$ 组成的集合为 $S$，则从 $S$ 中任取两个集合，从这两个集合中分别取一个元素 $x,y$，必然存在一个先从 $x$ 到环上，绕环一周，再到 $y$ 所在 SCC，最后到达 $y$ 的路径，因此 $S$ 应在同一个 $SCC$ 中，证毕。
### 关于强连通分量的一些应用
>$Question$:
>求最少选择几个点，使得信息可传递到所有点
>
>$Answer$:
>所有入度为 $0$ 的点，因为这些点无法通过其他点传递得到
>$Question$:
>求最少添加几条边，使得原图变为一个强连通分量
>
>$Answer$:
>先缩点，因为强连通分量之间可相互到达。既然要把使得这个图成为一个强连通分量，那么对于一个强连通分量来说，每个节点出入度不应该为 $0$，应该至少为 $1$,他们才能够形成强连通分量(因为入度为 $0$ 其他边无法到达，出度为 $0$，无法到达其他边),所以就是找出入度为 $0$ 的节点的个数，然后比较最大值即可。**（原图是一个强连通分量就为 $0$)**
# 双连通分量
## 边双连通分量
### 定义
在一张连通的无向图中，对于两个点 $u$ 和 $v$，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 $u$ 和 $v$ 边双连通。
对于一个无向图中的 **极大** 边双连通的子图，我们称这个子图为一个 **边双连通分量**。
边双连通具有传递性，即，若 $x$,$y$ 边双连通，$y$,$z$ 边双连通，则 $x$,$z$ 边双连通。
### Code
```
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#define N 500005
using namespace std;
int n,m;
vector<int> e[N];
int dfn[N],low[N],cnt,st[N],top;
int idx,bel[N];
vector<int> ans[N];
inline void read(int &x){
int f=1; char ch=getchar(); x=0;
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x*=f;
}
inline void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10) write(x/10);
putchar(x%10+'0');
}
inline void dfs(int u,int fa){
dfn[u]=low[u]=++cnt;
st[++top]=u;//维护新结点 u 的信息
for(int i=0;i<e[u].size();i++){
int v=e[u][i];
if(v==fa){//判重边与反向边技巧
fa=0;
continue;
}
if(!dfn[v]){//树边
dfs(v,u);//访问
low[u]=min(low[u],low[v]);//更新
}else{//非树边（前向边，返祖边，横叉边）
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){//找到一个边双
int v; idx++;
do{
v=st[top--];
ans[idx].push_back(v);
bel[v]=idx;
}while(v!=u);//加入&记录
}
}
int main(){
read(n); read(m);
for(int i=1;i<=m;i++){
int u,v; read(u); read(v);
e[u].push_back(v);
e[v].push_back(u);
}//建边
for(int i=1;i<=n;i++) dfs(i,0);//Tarjan
write(idx); putchar('\n');
for(int i=1;i<=idx;i++){
write(ans[i].size()); putchar(' ');
for(int j=0;j<ans[i].size();j++){
write(ans[i][j]); putchar(' ');
}
putchar('\n');
}//输出
return 0;
}
```
### 应用
求一张图加几条无向边使得这张图变为一个边双连通分量。
$ans=\lceil\frac{Leaf}{2}\rceil $($Leaf$ 为叶子连通块数)。
## 点双连通分量
### 定义
在一张连通的无向图中，对于两个点 $u$ 和 $v$，如果无论删去哪个点（只能删去一个）都不能使它们不连通，我们就说 $u$ 和 $v$ 点双连通。
对于一个无向图中的 **极大** 点双连通的子图，我们称这个子图为一个 **点双连通分量**。
点双连通**不**具有传递性。
### Code
```
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#define N 500005
using namespace std;
int n,m;
vector<int> e[N];
int dfn[N],low[N],cnt,st[N],top;
int idx,bel[N];
vector<int> ans[N];
inline void read(int &x){
int f=1; char ch=getchar(); x=0;
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x*=f;
}
inline void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10) write(x/10);
putchar(x%10+'0');
}
inline void dfs(int u,int fa){
dfn[u]=low[u]=++cnt;
st[++top]=u;//加入
int son=0;//儿子数
for(int i=0;i<e[u].size();i++){
int v=e[u][i];
if(v==fa){
fa=0;
continue;
}//判重边和反向边
if(!dfn[v]){
son++;
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){//找到一个点双连通分量
int vv; idx++;
bel[u]++;
ans[idx].push_back(u);//记录 u
do{
vv=st[top--];
bel[vv]++;
ans[idx].push_back(vv);
}while(vv!=v);//记录其他点（u 未被弹出，因为点双没有传递性，一个点可能属于多个点双）
}
}else{
low[u]=min(low[u],dfn[v]);
}
}
if(fa==-1&&son==0) ans[++idx].push_back(u);//判断孤立点带重边
}
int main(){
read(n); read(m);
for(int i=1;i<=m;i++){
int u,v; read(u); read(v);
if(u==v) continue;
e[u].push_back(v);
e[v].push_back(u);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
dfs(i,-1);
top=0;//根未被弹出，栈需清空
}
}
write(idx); putchar('\n');
for(int i=1;i<=idx;i++){
write(ans[i].size()); putchar(' ');
for(int j=0;j<ans[i].size();j++){
write(ans[i][j]); putchar(' ');
}
putchar('\n');
}
return 0;
}
```
# 割点
## 定义
对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点（又称割顶）。
一个点为割点当且仅当这个点属于一个以上的点双连通分量。
## Code
```
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#define N 20005
using namespace std;
int n,m;
vector<int> e[N];
int dfn[N],low[N],cnt,st[N],top;
int idx,bel[N];
int ans;
inline void read(int &x){
int f=1; char ch=getchar(); x=0;
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x*=f;
}
inline void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10) write(x/10);
putchar(x%10+'0');
}
inline void dfs(int u,int fa){//同点双连通分量
dfn[u]=low[u]=++cnt;
st[++top]=u;
int son=0;
for(int i=0;i<e[u].size();i++){
int v=e[u][i];
if(v==fa){
fa=0;
continue;
}
if(!dfn[v]){
son++;
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
int vv; idx++;
bel[u]++;//记录所属点双连通分量数
do{
vv=st[top--];
bel[vv]++;
}while(vv!=v);
}
}else{
low[u]=min(low[u],dfn[v]);
}
}
if(fa==-1&&son==0) idx++,bel[u]++;
}
int main(){
read(n); read(m);
for(int i=1;i<=m;i++){
int u,v; read(u); read(v);
if(u==v) continue;
e[u].push_back(v);
e[v].push_back(u);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) dfs(i,-1),top=0;
}
for(int i=1;i<=n;i++) ans+=(bel[i]>1);//记录答案
write(ans); putchar('\n');
for(int i=1;i<=n;i++){
if(bel[i]>1) write(i),putchar(' ');
}
return 0;
}
```
### 应用
>**例题**:[P3225 矿场搭建](https://www.luogu.com.cn/problem/P3225): 给定一张连通图，你可以设定 $k$ 个关键点，问: 要让删除一个任意点后，使得剩下的若干连通块都包含至少一个关键点，$k$ 的最小值是多少，和使得 $k$ 最小的方案数。
>
>1. 如果这个点双连通分量包含了 $1$ 个以上的割点，那么无论哪一个割点被堵，都可以通过其他割点逃向其他救生点，没有贡献答案。
>
>2. 如果这个点双连通分量只有 $1$ 个割点，如果割点被堵，就在点双连通分量内设立一个逃生点，如果逃生点被堵，就从割点出去。贡献为 $1$，方案数为 $size[i]-1$ （除去割点本身）。
>3. 如果这个点双连通分量没有割点。就要用两个逃生点互保。贡献为 $2$，方案数为 $size[i]*(size[i]-1)/2$。所有方案数乘起来就是答案。
# 后记
$update$ : $2025/7/30
$update$ : $2025/8/1 \hspace{0.18cm}$ 说明: 添加**关于强连通分量的一些应用**部分。
$update$ : $2025/8/6 \hspace{0.18cm}$ 说明: 添加**点/边双连通分量**和**割点**部分。