图的连通性专题
BingBang
·
·
个人记录
图的连通性
前置说明：
- 如无特别说明，G表示一个有向图。
- 如无特别说明，n表示G中节点数，m表示G中边数。
- 如无特别说明，(x,y)表示节点x，y间的一条路径，是否为有向路径依据讲解环境考虑。
有向图的连通性
定义与性质
强连通：在有向图G中，若两点u,v互相可达，则u,v强连通。若G中任意两点均强连通，则G为强连通图。
强连通分量：将G分为若干子图，每个子图内部强连通，且任意一个子图无法继续拓展（无法与子图外的点强连通），则每个子图称为G的一个强连通分量(SCC)。
也就是说，强连通分量具有强连通性和极大性。
- 定理：删除G中的一个强连通分量，不影响其他强连通分量的强连通性。
证明：设删除G中一个强连通分量G_1，对另一强连通分量G_2造成影响，这与G_2内部强连通性矛盾，不符合强连通分量定义。证毕。
- 定理：图G的所有强连通分量之间无交集。
证明：假设存在不同的强连通分量G_1,G_2 \in G，G_1 \cap G_2 \neq \varnothing，取u \in \complement _{G_1}^{G_1 \cap G_2}, v \in \complement _{G_2}^{G_1 \cap G_2},x \in G_1 \cap G_2 ，则u与x强连通，v与x强连通，则u,v强连通，不符合强连通分量G_1,G_2的极大性，与假设矛盾。证毕。
求法
Tarjin算法
算法原理：
- 定理：一个至少包含两个节点的强连通分量，从其中任意一个节点出发，至少一条路径能够回到该节点。
证明：设该节点为x，取强连通分量中另一节点y，由强连通分量定义知x可达y，y可达x，则(x,y),(y,x)即为符合条件的一条路径。证毕。
dfs生成树：
定义：任取节点为起始节点，对图的一个连通部分进行不重复访问节点的dfs，每条被使用的边与所有被访问的节点构成dfs生成树。
图片来源：教师（**不得转载或引用**）
- $dfs$形成栈：所有未分配归属强连通分量的节点形成$dfs$形成栈。
- 树边：每次$dfs$拓展一个未访问节点时经过的边称为一条树边。（连接未访问子节点）
- 回退边（返祖边）：在$dfs$过程中，当前节点访问的节点是已访问节点且在当前$dfs$形成的栈中，即目标节点为当前节点祖先，则经过的这条边称为回退边（返祖边）。（连接已访问祖先节点）
- 横叉边：在$dfs$过程中，当前节点访问的节点是已访问节点，但不在当前$dfs$形成栈中，也不在当前节点子树中，则经过的边称为横叉边。（连接已访问非祖先非子树节点）
- 前向边：在$dfs$过程中，当前节点访问的节点是已访问节点，且为当前节点已访问子树中的节点，则经过的边称为前向边。（连接已访问子树节点）
任取节点作为起始节点，进行$dfs$深度优先搜索。记录以下信息：
$id[x]$：节点$x$的$dfs$序。
$low[x]$：节点$x$的子树中的节点通过一条回退边（返祖边）或一条横叉边所能到达的节点的$id$值的最小值，且要求该$id$值对应的节点可以到达$x$。
注意到：满足上述条件的$id$值最小的节点一定在当前$dfs$栈内。否则该节点无法到达$x$。
$scc[x]$：节点$x$所在的强连通分量的人为定义编号。
###### 下面结合例题与代码讲解算法具体步骤。
例题：[间谍网络](https://www.luogu.com.cn/problem/P1262)
观察问题，发现将对每个间谍向其掌握的间谍连一条有向边，则生成有向图，在这个有向图中的任意一个强连通分量中，只要收买任意一个间谍，就能掌握强连通分量中所有间谍的犯罪证据。同时，若一个强连通分量存在一条前往另一强连通分量中的边，则只需要掌握起点强连通分量中的间谍，就可以掌握终点强连通分量的所有间谍。贪心法即可求解。
首先使用强连通分量的$Tarjin$算法缩点，对于缩点后的图，对每个入度为$0$的点求其中包含节点的最小代价，最小代价之和即为答案。特别地，如果存在一个入度为$0$的点，其中的节点均无法被收买，则问题无解。
示例代码：
```
#include<bits/stdc++.h>
using namespace std;
#define re register
#define N 3005
#define M 8005
int n,p,m,money[N];
vector<int>a[N];//邻接表存图
int id[N],low[N],scc[N],sc,cnt;
//id:dfs序 low:最小到达节点 scc:所属强连通分量编号 sc:编号计数 cnt:dfs序计数
stack<int>s;
bool ins[N];//是否在栈内
vector<int>scp[N];//记录每个强连通分量内节点
void tarjin(int x){
id[x]=low[x]=++cnt;
s.push(x);ins[x]=1;
for(re int i=0;i<a[x].size();i++){
re int v=a[x][i];
if(!id[v]){//经过树边访问未访问子节点
tarjin(v);
low[x]=min(low[x],low[v]);//更新low值
}else if(!scc[v]){//经过一条返祖边或横叉边更新low值
//若目标节点scc=0，即还未确定所属强连通分量，
//则目标节点与当前节点属于同一强连通分量，且目标节点在栈内
low[x]=min(low[x],id[v]);//仅能经过一条边
}
}
if(id[x]==low[x]){//子树内节点无法通过返祖边或横叉边访问非子树内节点，故当前栈内节点构成一个极大强连通分量
re int v=s.top();s.pop();ins[v]=0;
scc[v]=++sc;
scp[sc].push_back(v);
while(v!=x){
v=s.top();s.pop();ins[v]=0;
scc[v]=sc;
scp[sc].push_back(v);
}
}
return ;
}
int in[N];//记录缩点入度
int main(){
scanf("%d%d",&n,&p);memset(money,127,sizeof(money));
for(re int i=1,u;i<=p;i++){
scanf("%d",&u);
scanf("%d",&money[u]);
}
scanf("%d",&m);
for(re int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
a[u].push_back(v);//邻接表存边
}
for(re int i=1;i<=n;i++){
if(!id[i]){//未遍历
tarjin(i);//dfs遍历
}
}
for(re int i=1;i<=sc;i++){//遍历所有强连通分量
for(re int j=0;j<scp[i].size();j++){//遍历强连通分量内节点
re int v=scp[i][j];
for(re int k=0;k<a[v].size();k++){//遍历节点连边
if(scc[a[v][k]]!=i){//找到缩点之间的边
in[scc[a[v][k]]]++;
}
}
}
}
re int ans=0,minip=INT_MAX;
for(re int i=1;i<=sc;i++){
if(!in[i]){
int minn=INT_MAX,minid=INT_MAX;
for(re int j=0;j<scp[i].size();j++){
minn=min(minn,money[scp[i][j]]);
minid=min(minid,scp[i][j]);
}
if(minn>20000){
minip=min(minip,minid);
}else{
ans+=minn;
}
}
}
if(minip==INT_MAX){
puts("YES");
printf("%d",ans);
}else{
puts("NO");
printf("%d",minip);
}
return 0;
}
```
##### 缩点：
定义：将有向图中的每个强连通分量视为一个节点构成新点集，不同强连通分量的节点之间的边构成新边集，则形成的新图称为原图的缩点图。每个节点是原图强连通分量的缩点。
观察缩点后的图，发现是一个$DAG$（若存在环，则环内点互相可达，属于同一强连通分量，不符合缩点及强连通分量定义），故可以使用许多适用于$DAG$图的算法解决问题。
模板题：
[消息扩散](https://www.luogu.com.cn/problem/P2002)
[受欢迎的牛](https://www.luogu.com.cn/problem/P2341)
典型例题：
[[中山市选]杀人游戏](https://www.luogu.com.cn/problem/P4819)
[[SCOI2011]糖果](https://www.luogu.com.cn/problem/P3275)
### 无向图的连通性
#### 定义与概念
连通分量：无向图中，所有能互相连通的点组成一个连通分量。
割点：删除后会使图中连通分量个数增加的点称为割点。
割边：删除后会使图中连通分量个数增加的边称为割边。
点双连通：无向图中的两点之间存在至少两条除起点、终点外无公共点的路径，则这两点点双连通。
点双连通子图：对于原图的一个子图，若子图内任意两点点双连通，则称这个子图是点双连通子图。
点双连通分量：一个点双连通的子图中的任意点若无法与子图外的点点双连通，则称这个子图为原图的一个点双连通分量。具体地说，点双连通分量是极大的点双连通子图。
边双连通：无向图中的两点之间存在至少两条无公共边路径，则这两点边双连通。
边双连通子图：选取原图的一个子图，若子图内任意两点边双连通，则称这个子图是边双连通子图。
边双连通分量：一个边双连通的子图中的任意点无法与子图外的点边双连通，则称这个子图为原图的一个边双连通分量。具体地说，边双连通分量是极大的边双连通子图。
$dfs$生成树：定义同有向图连通性中定义。
#### 边的分类
类似于有向图的连通性，我们对边进行分类：
树边：$dfs$过程中经过的边。
回退边（返祖边）：$dfs$过程中访问已访问节点所经过的边。
由于无向图中只要两点间有边，则两点必定互相可达，故无向图中不存在横叉边与前向边。
#### 割点、割边算法
- 定理：$dfs$生成树的根节点$s$是割点，当且仅当$s$有至少$2$个子节点。
>充分性证明：当$s$为割点时，设$s$仅有$1$个子节点，由$dfs$性质知该子节点及其后代互相连通，则$s$删除后不影响其他节点连通性，$s$不为割点，与假设矛盾。证毕。
>必要性证明：由$dfs$性质可知：$s$的不同子节点之间不相互连通，故删除$s$后，子节点之间不互相连通。$s$的子节点数量不少于$2$时$s$为割点。证毕。
- 定理：$dfs$生成树的非根节点$u$为割点，当且仅当$u$的一个子节点$v$及其后代均不存在到达$u$祖先的回退边。
>充分性证明：若$u$的所有子节点及其后代均存在返回$u$祖先的边，则$u$删除后根节点均能通过返回$u$祖先的边与其他节点相连，$u$不为割点，与假设矛盾。证毕。
>必要性证明：删除$u$后，由于$v$及其后代均无到达$u$祖先的回退边，故$v$及其后代与$dfs$生成树上其他节点之间不互相可达，当$u$不为根节点时$dfs$生成树上除$v$及其后代外仍有节点，故$u$为割点。
在$dfs$过程中，记录以下信息：
$id[x]$：节点$x$的$dfs$序。
$low[x]$：节点$x$通过一条回退边（返祖边）能达到的最小$id$值节点的$id$值。
若对于一个非根节点$x$的子节点$y$，有$id[x] \leq low[y]$，则由上述定理知$x$为割点。
特别地，若$id[x] < low[y]$，则边$(x,y)$为割边。
###### 非树边、重边不可能为割边。证明方法显然。
##### 代码实现
模板题：[【模板】割点（割顶）](https://www.luogu.com.cn/problem/P3388)
```
#include<bits/stdc++.h>
using namespace std;
#define re register
#define M 20005
int n,m;
vector<int>a[M];
int id[M],low[M],fa[M],cnt,ans;
bool cut[M];
void tarjin(int x,int root){
id[x]=low[x]=++cnt;
re int child=0;//记录子节点数量，用于根节点统计
for(re int i=0;i<a[x].size();i++){
re int v=a[x][i];
if(!id[v]){//经过一条树边访问子节点
fa[v]=x;child++;
tarjin(v,root);
low[x]=min(low[x],low[v]);
if(!cut[x]&&id[x]<=low[v]&&x!=root){//割点判定
cut[x]=1;ans++;
}
}else if(id[v]<id[x]&&v!=fa[x]){
low[x]=min(low[x],id[v]);
//通过一条回退边（返祖边）到达祖先，且祖先不为父节点
}
}
if(!cut[x]&&x==root&&child>=2){
cut[x]=1;ans++;
}
return ;
}
int main(){
scanf("%d%d",&n,&m);
for(re int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
a[u].push_back(v);
a[v].push_back(u);
}
for(re int i=1;i<=n;i++){
if(!id[i]){
tarjin(i,i);
}
}
printf("%d\n",ans);
for(re int i=1;i<=n;i++){
if(cut[i]){
printf("%d ",i);
}
}
return 0;
}
```
典型例题：[[POI2008]BLO-Blockade](https://www.luogu.com.cn/problem/P3469)
#### 边双连通分量算法
问题：对于一个无向图，添加若干条边，使得图变为边双连通图，求最小添加边数。
- 定理：每个节点仅属于一个边双连通分量。
>证明：设节点$u$属于边双连通分量$G_1,G_2$，则$u$与$x \in G_1,x \neq u$边双连通，$u$与$y \in G_2,y \neq u$边双连通，则$x,y$边双连通，与边双连通分量极大性矛盾。证毕。
- 定理：边双连通分量中无割边。
>证明：设边双连通分量中存在一条割边，则割边连接的两节点在割边删除后仍可通过另一路径相连，不符合割边定义。证毕。
由于每个节点仅属于一个边双连通分量，我们将同属于一个边双连通分量的节点视为一个点（缩点），使原图变为一棵树（证明如下）。
- 定理：无向连通图中所有边双连通分量及连接不同边双连通分量中节点的边构成的图是树。
>证明：由于原图连通，故只需证明原图中无环路即可。
假设原图有环，则对于两个在同一环路上且属于不同边双连通分量的节点$u,v$，由于$u,v$在同一环路上，故$u,v$间边双连通，不符合边双连通分量的极大性。证毕。
- 定理：$low$值相等的节点属于同一边双连通分量。
>证明：$low$值为节点通过一条非树边所能到达的$dfs$序最小的节点的$dfs$序。两节点$low$值相等，则两节点间除通过树边相连外，还可通过非树边相连，故两节点边双连通，根据边双连通分量极大性可知两节点属于同一边双连通分量。证毕。
为使任意两个边双连通分量之间边双连通，任取非叶节点作为根节点，每个边双连通分量除前往根节点的唯一路径外，还需有另一路径。贪心法可知最佳路径为连接叶节点的路径。即使叶节点两两配对相连（无法配对的直接连向任意叶节点），即可使任意边双连通分量之间边双连通（一条路径是前往根节点的路径，另一路径经过叶节点之间的边相连），故最小添加边数为$int((叶节点个数+1)/2)$。
##### 例题及示例代码
例题：[[USACO06JAN]Redundant Paths G](https://www.luogu.com.cn/problem/P2860)
示例代码：
```
#include<bits/stdc++.h>
using namespace std;
#define re register
#define M 5005
int n,m;
vector<int>a[M];
int id[M],low[M],cnt,fa[M];
vector<int>ecc[M];
bool vis[M][M],vip[M][M];
void tarjin(int x){
if(!vip[x][fa[x]])id[x]=low[x]=++cnt;
else id[x]=++cnt,low[x]=low[fa[x]];
for(re int i=0;i<a[x].size();i++){
re int v=a[x][i];
if(!id[v]){
fa[v]=x;
tarjin(v);
low[x]=min(low[x],low[v]);
}else if(v!=fa[x]){
low[x]=min(low[x],id[v]);
}
}
ecc[low[x]].push_back(x);
return ;
}
int in[M];
struct node{
int p,q;
};
vector<node>d;
int f[M];
inline int getfa(int x){
return f[x]==x?x:f[x]=getfa(f[x]);
}
int main(){
scanf("%d%d",&n,&m);
for(re int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
if(vis[u][v]){
vip[u][v]=vip[v][u]=1;
cerr<<"Error!";
}
vis[u][v]=vis[v][u]=1;
a[u].push_back(v);
a[v].push_back(u);
}
tarjin(1);
for(re int i=1;i<=n;i++){
for(re int j=0;j<ecc[i].size();j++){
re int v=ecc[i][j];
for(re int k=0;k<a[v].size();k++){
if(low[a[v][k]]!=i){
in[low[a[v][k]]]++;
}
}
}
}
re int ans=0;
for(re int i=1;i<=n;i++){
if(in[i]==1){
ans++;
}
}
printf("%d",(ans+1)/2);
return 0;
}
```
注意事项：
- 出现重边时，重边所连接的两节点属于同一边双连通分量，在$dfs$时应特殊注意。
##### 例题
- 给定无向连通图，询问节点$u,v$间桥的数量。
解决方法：求出原图边双连通分量，将原图转化为树，对$u,v$节点对应边双连通分量进行树上倍增或树链剖分求路径长度即可。
- 给定无向连通图，允许进行操作：增加无向边$(u,v)$，询问$u,v$间桥的数量。
解决方法：增加无向边$u,v$后，$u,v$所在边双连通分量到两者$LCA$路径上的桥均无效（合并为一个边双连通分量），故可使用树链剖分解决。
- 给定无向连通图，允许删除无向边，保证任意时刻图连通，询问$u,v$间桥的数量。
解决方法:操作及询问倒序处理，删边操作变为加边操作。
解决该问题的技巧还有:开始建成一棵树，将未使用的边作为加边操作处理。
#### 点双连通分量算法
##### 部分定理及证明
- 定理：点双连通分量内部无相对点双连通分量内部的割点。
>证明：设一个点双连通分量中存在某个割点，则删除该点后，由点双连通分量定义，该点双连通分量内任意两点除经过该割点的路径外，至少有一条不经过该割点的路径使这两点互相可达，不符合割点定义。证毕。
- 定理：一条边连接的两节点属于同一点双连通分量。
>证明：由定义可得。
- 定理：每条边仅属于一个点双连通分量。
>证明：由于一条边连接的两节点属于同一点双连通分量，故该边属于这一点双连通分量。
需要特别注意的是：一个点可以属于多个点双连通分量。
- 定理：割点属于两个点双连通分量，属于两个点双连通分量的点必定为割点。
>证明：暂略。
##### 圆方树
定义：对每个点双连通分量，建立一个特殊节点，该特殊节点与该点双连通分量内所有节点间均有一条无向边，则特殊节点及新增无向边与原点集（删除原边集）构成的图为圆方树。
建立方法：在求点双连通分量（割点）时，每次找到一个割点，就将一个新的特殊节点与此时栈内节点$x$至栈顶的所有节点连边。需要特别注意的是：$x$不能被弹出栈。
示例代码：
```
#include<bits/stdc++.h>
using namespace std;
#define re register
#define N 200005
int n,m,q;
vector<int>a[N],b[N];//存储原图边/存储圆方树边
int id[N],low[N],fa[N];
stack<int>s;
int cnt,tot;//dfs序/方形点编号计数
void tarjin(int x){
id[x]=low[x]=++cnt;
s.push(x);
for(re int i=0;i<a[x].size();i++){
re int v=a[x][i];
if(!id[v]){
fa[v]=x;
tarjin(x);
low[x]=min(low[x],low[v]);
if(id[x]<=low[v]){//找到割点
tot++;//新建圆方树节点
re int p;
do{
p=s.top();s.pop();
b[tot].push_back(p);
b[p].push_back(tot);//新增圆方树边
}while(p!=v);//当前节点x不弹出
b[tot].push_back(x);
b[x].push_back(tot);
}
}else if(v!=fa[x]){
low[x]=min(low[x],id[v]);
}
}
return ;
}
int main(){
scanf("%d%d%d",&n,&m,&q);
for(re int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
a[u].push_back(v);
a[v].push_back(u);
}
tot=n;
tarjin(1);
}
```
###### 性质：
- 圆方树上任意一条边所连接的节点为不同类型（圆点/方点）节点。
>证明：由建图过程易知。
- 原图的割点为圆方树上度数大于$1$的圆点。
>证明：方点不在原图上，故割点必为圆点。圆点度数大于$1$，由上述性质知其连接至少两个方点，即连接至少两个点双连通分量，故该点为割点。
- 以不同节点为根建立的圆方树形态相同。
>证明：暂略。
上方定理表明：圆方树是无根树。
##### 例题：
- 给定无向连通图，询问两条边之间的所有路径的公共点。
解决方法：对原图建立圆方树，使用树链剖分算法即可求解。
# 未完待续。