专栏文章

连通性问题

SSkyDreamer
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miom6jsh
此快照首次捕获于
2025/12/02 21:28
3 个月前
此快照最后确认于
2025/12/02 21:28
3 个月前
查看原文

强连通分量

定义

强连通的定义是：有向图 GG 强连通是指，GG 中任意两个结点连通。
强连通分量（StronglyStrongly ConnectedConnected ComponentsComponents，SCCSCC）的定义是：极大的强连通子图。

Tarjan 算法

DFS 生成树

在介绍该算法之前，先来了解 DFS 生成树，我们以下面的有向图为例：
有向图的 DFSDFS 生成树主要有 44 种边（不一定全部出现）：
  1. 树边（treeedgetree edge）：示意图中以黑色边表示，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
  2. 反祖边（backedgeback edge）：示意图中以红色边表示（即 77 至 11），也被叫做回边，即指向祖先结点的边。
  3. 横叉边（crossedgecross edge）：示意图中以蓝色边表示（即 99 至 77），它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点 并不是 当前结点的祖先。注意:起点的 dfndfn 大于终点的 dfndfn。
  4. 前向边（forwardedgeforward edge）：示意图中以绿色边表示（即 33 至 66），它是在搜索的时候遇到子树中的结点的时候形成的。
我们考虑 DFSDFS 生成树与强连通分量之间的关系。
如果结点 uu 是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 uu 为根的子树中。结点 uu 被称为这个强连通分量的根。

Tarjan 算法求强连通分量

TarjanTarjan 算法基于对图进行深度优先搜索。我们视每个连通分量为搜索树中的一棵子树，在搜索过程中，维护一个栈，每次把搜索树中尚未处理的节点加入栈中。
在 TarjanTarjan 算法中为每个结点 uu 维护了以下几个变量：
dfnudfn_u : uu 的 dfsdfs 序。
lowulow_u : 在 uu 的子树中能够回溯到的最早的已经在栈中的结点。设以 u 为根的子树为 Subtreeu{Subtree}_u。lowu{low}_u 定义为以下结点的 dfndfn 的最小值：SubtreeuSubtree_u 中的结点；从 SubtreeuSubtree_u 通过一条不在搜索树上的边能到达的结点。不过可淡化其意义，变成辅助合并的标志。
显而易见，一个结点的子树内结点的 dfndfn 都大于该结点的 dfndfn。
从根开始的一条路径上的 dfndfn 严格递增，lowlow 严格非降。
按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索，维护每个结点的 dfndfn 与 lowlow 变量，且让搜索到的结点入栈。每当找到一个强连通元素，就按照该元素包含结点数目让栈中元素出栈。在搜索过程中，对于结点 uu 和与其相邻的结点 vv（vv 不是 uu 的父节点）考虑 33 种情况：
  1. vv 未被访问：继续对 vv 进行深度搜索。在回溯过程中，用 lowvlow_v 更新 lowulow_u。因为存在从 uu 到 vv 的直接路径，所以 vv 能够回溯到的已经在栈中的结点，uu 也一定能够回溯到。
  2. vv 被访问过，已经在栈中：根据 lowlow 值的定义，用 dfnvdfn_v 更新 lowulow_u。
  3. vv 被访问过，已不在栈中：说明 vv 已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。

Code

CPP
#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)O(n+m)。

拓扑排序

考察 TarjanTarjan 中被最优先处理的是什么样的点，发现显然就是那些没有出度的点，而这和拓扑排序反全是反过来的。而又因为我们的 SCCSCC 编号是按顺序排的，所以本质上相当于把拓扑序反了过来。
因此，SCC 编号等于逆拓扑序。
但DP 转移顺序应为拓扑序

一些结论

一个有向图中，如果将所有强连通分量缩成一个点，则这个图一定无环。即为 DAGDAG 图。

证明

反证，假设这个图中有环，环上的点代表的 SCCSCC 组成的集合为 SS，则从 SS 中任取两个集合，从这两个集合中分别取一个元素 x,yx,y，必然存在一个先从 xx 到环上，绕环一周，再到 yy 所在 SCC，最后到达 yy 的路径，因此 SS 应在同一个 SCCSCC 中，证毕。

关于强连通分量的一些应用

QuestionQuestion:
求最少选择几个点，使得信息可传递到所有点
AnswerAnswer: 所有入度为 00 的点，因为这些点无法通过其他点传递得到
QuestionQuestion:
求最少添加几条边，使得原图变为一个强连通分量
AnswerAnswer: 先缩点，因为强连通分量之间可相互到达。既然要把使得这个图成为一个强连通分量，那么对于一个强连通分量来说，每个节点出入度不应该为 00，应该至少为 11,他们才能够形成强连通分量(因为入度为 00 其他边无法到达，出度为 00，无法到达其他边),所以就是找出入度为 00 的节点的个数，然后比较最大值即可。（原图是一个强连通分量就为 00)

双连通分量

边双连通分量

定义

在一张连通的无向图中，对于两个点 uu 和 vv，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 uu 和 vv 边双连通。
对于一个无向图中的 极大 边双连通的子图，我们称这个子图为一个 边双连通分量。
边双连通具有传递性，即，若 xx,yy 边双连通，yy,zz 边双连通，则 xx,zz 边双连通。

Code

CPP
#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=⌈Leaf2⌉ans=\lceil\frac{Leaf}{2}\rceil (LeafLeaf 为叶子连通块数)。

点双连通分量

定义

在一张连通的无向图中，对于两个点 uu 和 vv，如果无论删去哪个点（只能删去一个）都不能使它们不连通，我们就说 uu 和 vv 点双连通。
对于一个无向图中的 极大 点双连通的子图，我们称这个子图为一个 点双连通分量。
点双连通不具有传递性。

Code

CPP
#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

CPP
#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 矿场搭建: 给定一张连通图，你可以设定 kk 个关键点，问: 要让删除一个任意点后，使得剩下的若干连通块都包含至少一个关键点，kk 的最小值是多少，和使得 kk 最小的方案数。
  1. 如果这个点双连通分量包含了 11 个以上的割点，那么无论哪一个割点被堵，都可以通过其他割点逃向其他救生点，没有贡献答案。
  2. 如果这个点双连通分量只有 11 个割点，如果割点被堵，就在点双连通分量内设立一个逃生点，如果逃生点被堵，就从割点出去。贡献为 11，方案数为 size[i]−1size[i]-1 （除去割点本身）。
  3. 如果这个点双连通分量没有割点。就要用两个逃生点互保。贡献为 22，方案数为 size[i]∗(size[i]−1)/2size[i]*(size[i]-1)/2。所有方案数乘起来就是答案。

后记

updateupdate : 2025/7/302025/7/30
updateupdate : 2025/7/312025/7/31 说明: 增加代码实现。
updateupdate : 2025/8/12025/8/1 \hspace{0.18cm} 说明: 添加关于强连通分量的一些应用部分。
updateupdate : 2025/8/62025/8/6 \hspace{0.18cm} 说明: 添加点/边双连通分量和割点部分。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...