【图论】图的连通性
PhainonK
·
·
算法·理论
upd：再次完善此内容已经是2024年再次复习了。希望比之前有更多理解。
图论基础概念
- 在无向图中，若任意两点互相可达，则称该图为连通图。
如图，每两个点之间均有路径相连。
有向图的连通性
前置知识： 拓扑排序
定义&概念
强连通： 若一个有向图 G 中任意两点互相可达，则称有向图 G 强连通，有向图 G 是一个强连通图。
强连通分量（SCC）： 极大强连通子图。
极大，“大的不能再大了”。即为添加图中任意点或边，该子图都不再强连通。
还是直接上算法吧。
求强连通分量-Tarjan
别的算法不再多讲。
Tarjan 的核心就是边分类，转移。
以下几种边：
- 树边。正常的树边，一般按遍历顺序确定。
- 反祖边。由子树中的节点返回祖先的边。这种边是 Tarjan 算法中求强连通分量的核心边。
- 横跨边。两颗不同子树之间的连边。在求 SCC 中无用。
- 前向边。从祖先连向后代。无用。
放图。
图中边上的编号即对应上文提到的边分类。
显然图中有三个强连通分量：\{1,3,7\}，\{2,4,6\}，\{5\}。
可以发现，总是“反祖边”将几个点组成强连通分量。
上写了一下午的注释代码。（好像通过这个确实深入理解了呢！）
```c
//有向图求强连通分量个数、强连通分量中的节点等问题
#include<bits/stdc++.h>
using namespace std;
const int N=10010;//N的值随题目变化
int n,m,cnt=0,ans=0;
//n:节点个数 m:边条数 cnt:时间戳 ans:强连通分量数量
vector<int> maps[N];//邻接表存边关系
stack<int> s;//存节点的栈，从中取出强连通分量中的节点
int low[N],dfn[N],f[N],rd[N],sum[N];
//low[i]:第i个节点可到达或其子树可到达的开始时间最早的节点的开始时间
//dfn[i]:第i个节点的开始时间 f[i]:第i个节点所属的强连通分量编号
//rd[i]:第i个强连通分量的入度（缩点时使用） sum[i]:第i个强连通分量中的节点个数
bool vis[N],Is[N];
//vis[i]:第i个节点在Tarjan中是否被到达过（可优化）
//Is[i]:第i个节点是否在栈中
vector<int> K[N];
//K[i]:第i个强连通分量中的节点
void Tarjan(int x){
dfn[x]=low[x]=++cnt;
//到达一个节点，dfn和low的值赋为时间戳
s.push(x);//节点入栈
Is[x]=vis[x]=true;//标记（入栈，已到达）
for(int i=0;i<maps[x].size();i++){//遍历x的每一个子节点
int v=maps[x][i];
if(!vis[v]){//该子节点未被到达
Tarjan(v);//继续深搜
low[x]=min(low[x],low[v]);//更新low值
//此时该子节点的子树已被全部遍历过，该子节点low值已经确定
//若low[x]在此时被更新，说明该子节点或该子节点的子树中的节点有返祖边
//且此返祖边返祖到达的点必定是x上的点，x理应被更新
}
else if(Is[v]){//若该子节点已被到达
//说明该子节点一定在x上方，被先找到过，这里是一条返祖边
low[x]=min(low[x],dfn[v]);//更新low值
//low值的定义是能到达的开始时间最早的节点的开始时间，因此为返祖现象，
//则v的开始时间一定早于x的开始时间，所以理应更新low值
}
}
if(low[x]==dfn[x]){
//当low与dfn相等，则该节点的low值没有更新
//则该节点的子树没有返祖现象或返祖现象最高到达该节点，构成一个强连通分量
ans++;//强连通快个数增加（同时ans也可以作为当前编号）
int d;
do{
d=s.top();//取出栈顶元素（此时栈内元素到x截止均为此 强连通分量的节点）
s.pop();
Is[d]=false;//标记
f[d]=ans;//d的强连通分量编号为ans
sum[ans]++;//编号为ans的强连通分量数量增加
K[ans].push_back(d);//将d存入该强连通分量
}while(d!=x);//do-while的使用是“先做再判断可行性”
//等于while(d!=x){}后再取出栈顶元素x
}
return ;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
maps[x].push_back(y);//vector存图
}
for(int i=1;i<=n;i++){
if(!vis[i]) Tarjan(i);//此处题目中若保证是一个连通图，则只用深搜一次：Tarjan(root)
}
for(int i=1;i<=n;i++){
for(int j=0;j<maps[i].size();j++){
//缩点，把每个强连通分量缩为一个点，通过各个分量之间的关系构成一个拓扑排序
int v=maps[i][j];
if(f[i]!=f[v]) rd[f[v]]++;//不属于同一个强连通分量，则被指向的连通块增加入度
}
}
//最终结果：
printf("强连通分量数量：%d\n",ans);
printf("各个节点所属强连通分量编号：\n");
for(int i=1;i<=n;i++){
printf("%d ",f[i]);
}
printf("\n");
printf("各个强连通分量的节点：\n");
for(int i=1;i<=ans;i++){
printf("第%d个强连通分量节点个数：%d\n",i,sum[i]);//个数可用K[i].size()代替
printf("节点：");
for(int j=0;j<K[i].size();j++){
printf("%d ",K[i][j]);
}
printf("\n");
}
return 0;
}
```
不多解释了。
# 无向图连通性
主要是**点双连通分量**和**边双连通分量**。
都可以用 Tarjan 解决。
## 点双连通分量
与求割点一起应用。
割点判断条件：`if(low[v]>=dfn[u])`
根据 $low$ 和 $dfn$ 的定义，此处意为 $u$ 的子节点 $v$ 最早能到达的点不超过当前点 $u$，所以删去点 $u$，$v$ 及其子树将与其他节点不连通，所以 $u$ 为割点。
因为割点属于多个点双，所以后面求点双时需将当前割点 $u$ 重复入栈。
但是如果实现时用边实现，则不需要重复入栈。
> 原因：每一条边仅属于一个点双连通分量。
```cpp
//从题解区hao的代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, M = 4e6 + 5;
int cnt = 1, fir[N], nxt[M], to[M];
int s[M], top, bcc, low[N], dfn[N], idx, n, m;
vector<int> ans[N];
inline void tarjan(int u, int fa) {
int son = 0;
low[u] = dfn[u] = ++idx;
s[++top] = u;
for(int i = fir[u]; i; i = nxt[i]) {
int v = to[i];
if(!dfn[v]) {
son++;
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u]) {
bcc++;
while(s[top + 1] != v) ans[bcc].push_back(s[top--]);//将子树出栈
ans[bcc].push_back(u);//把割点/树根也丢到点双里
}
} else if(v != fa) low[u] = min(low[u], dfn[v]);
}
if(fa == 0 && son == 0) ans[++bcc].push_back(u);//特判独立点
}
inline void add(int u, int v) {
to[++cnt] = v;
nxt[cnt] = fir[u];
fir[u] = cnt;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
for(int i = 1; i <= n; i++) {
if(dfn[i]) continue;
top = 0;
tarjan(i, 0);
}
printf("%d\n", bcc);
for(int i = 1; i <= bcc; i++) {
printf("%d ", ans[i].size());
for(int j : ans[i]) printf("%d ", j);
printf("\n");
}
return 0;
}
```
## 边双连通分量
与求割边一起应用。
割边判断条件：`if(low[v]>dfn[u])`
此处与求割点的区别在于符号，原因是当前求的割边是 $(u,v)$，若 $v$ 可以到达 $u$ ，则此边不是割边，所以符号为 $>$ 。
2024.2.14 ~~（情人节）~~ 写的代码，将就看吧。
这里的做法是先求出割边，再 dfs 求出边双。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=2e6+10;
int n,m,cnt=0,cc=0;
int head[N];
struct node{
int nxt,t;
}g[M*2];
void add(int x,int y){
g[cnt].t=y;
g[cnt].nxt=head[x];
head[x]=cnt;
cnt++;
return ;
}
int dfn[N],low[N],f[N];
bool flag[M*2];
void Tarjan(int x,int fa){
dfn[x]=low[x]=++cnt;
for(int i=head[x];i!=-1;i=g[i].nxt){
int v=g[i].t;
if(v==fa) continue;
if(!dfn[v]){
Tarjan(v,x);
low[x]=min(low[x],low[v]);
if(low[v]>dfn[x]) flag[i]=flag[i^1]=true;
}
else low[x]=min(low[x],dfn[v]);
}
return ;
}
int now=0;
bool vis[M*2],mark[N];
void dfs(int x){
f[x]=now;
for(int i=head[x];i!=-1;i=g[i].nxt){
int v=g[i].t;
if(vis[i]||flag[i]) continue;
vis[i]=vis[i^1]=true;
dfs(v);
}
return ;
}
vector<int> k[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) head[i]=-1;
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
cnt=0;
for(int i=1;i<=n;i++){
if(!dfn[i]) Tarjan(i,0);
}
for(int i=1;i<=n;i++){
if(!f[i]){
now++;
dfs(i);
}
k[f[i]].push_back(i);
}
printf("%d\n",now);
for(int i=1;i<=now;i++){
printf("%d ",k[i].size());
for(int j=0;j<k[i].size();j++) printf("%d ",k[i][j]);
printf("\n");
}
return 0;
}
```
# 题目收获
实际上都没有什么好讲的。
一般来说，题目套路：属于一个强/点双/边双连通分量的节点可以一起计算贡献/有特殊性质等，然后 Tarjan 求解，缩点，最后拓扑求解答案。
仍然是如何将题目转化为图的建图过程尤为重要。