连通分量
inoichi_lim
2020-04-16 18:40:04
## 1. 前言
有错误的话请在评论区提出，谢谢
## 2. 连通图&连通分量
在无向图的节点$v_i$和$v_j$中若$v_i$和$v_j$有路径相连，那么$v_i$和$v_j$连通。
若无向图$G$中的任意$v_i$和$v_j$连通，则$G$是连通图。
现在定义$G$的连通分量（即$G$的极大连通子图）为$G$的一个子图，并且若再在$G$上加一个顶点，该子图不连通。
对于连通图，起连通分量就是自己；否则，该图至少有$3$个连通分量。
对于有向图，若所有节点$v_i$和$v_j$中若$v_i$和$v_j$，$v_j$，$v_i$有路径相连，该图是强连通图。
有向图$G$的极大连通子图为$G$的强连通分量。
## 3. 割点&割边（桥）
定义就不说了。
这里说一些割点，割边的性质：
- 有割点不一定有割边，有割边一定有割点；
- 割边一定是割点所连接的边。
## 4. 双连通分量（DCC）
若一个图**没有割边**，则该图为**边双连通图**。
若一个图**没有割点**，则该图为**点双连通图**。
同理，无向图的极大边双连通图称为边双连通分量（`e-DCC`），无向图的极大点双连通图称为点双连通分量（`v-DCC`）。
## 5. 缩点
将无向图的**每一个边双连通分量**看成一个点，把所有连到这个连通分量的边全部连向这个新的点，称为缩点，这样，我们就可以得到一棵树。
原因：显然每一个边双连通分量都是一个环，把边双连通分量删去后就等同于把所有环都删去了，所以就可以得到一棵树了。
然后，不难发现，树的边就是割边。所以，边双连通分量就是图删去割边后留下的连通块。
将无向图的割点看做一个点，每一个点双连通分量看做一个点，把每一个割点向包含自己的点双连通分量连一条边，得到一棵树。
## 6. Tarjan算法
变量定义：
- $dfn_i$表示点$i$是深度优先遍历第几个遍历到的。
- $low_i$表示$i$或$i$的子孙可以通过非父子边追溯到的$dfn$最小的节点编号。
初始时，$dfn_i=low_i$。
默认深度优先遍历从点$1$开始。
接下来，删去目前的路径，检查$k$点能否到达$1,2...$点，如果能的话，$low_k=\min(low_k,dfn_{\min{k|k\text{能到达的所有的点的最小值}}})$。
然后，$k$的所有祖先的$low$都可以快乐地更新喽qwq
### 6.1. Tarjan求割边
若**无向**边$(x,y)$是割边，那么当且仅当搜索树上存在$x$的一个**子节点**$y$，使得：
$$dfn_x<low_y$$
代码：
```cpp
#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=200001,inf=0x3f3f3f3f;
struct bian{
int next,to;
bian(){
next=0;
}
}e[N];
int n,m,dfn[N],low[N],num,head[N],totm,ans,anss[N];
void add(int s,int ed){
e[++totm].next=head[s];
e[totm].to=ed;
head[s]=totm;
}
void tarjan(int now,int fa){
dfn[now]=low[now]=++num;
for(int i=head[now];i;i=e[i].next){//访问
int k=e[i].to;
if(k==fa) continue;//遍历过了/kk
if(dfn[k]==0){//new point
tarjan(k,now);//继续遍历
low[now]=min(low[now],low[k]);//更新，去最小值
if(low[k]>dfn[now]){
//回不去了/kk
//这里now-k是割边
cout<<now<<"and"<<k<<endl;
}
}else low[now]=min(low[now],dfn[k]);//更新。
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
fs(i,1,m,1){
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
}
//totm--;
fs(i,1,n,1){
if(dfn[i]==0){//还没被访问过
tarjan(1,0);//遍历去~
}
}
cout<<ans<<'\n';
sort(anss+1,anss+ans+1);
fs(i,1,ans,1) cout<<anss[i]<<' ';
return 0;
}
```
而割点，只要把上面的$<$改成$\le$即可。
但是，还要考虑一种情况。
```
3 2
1 2
1 3
```
这里**虽然$1$是割点，但是程序会误判为$3$个都是割点！！！**
原因很简单：你这里掐掉这条边和这点（实际上没有删除）后确实会分割成两个部分，可是事实上**他已经删掉了，还是只有一个部分！！！**
代码：
```cpp
#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=200001,inf=0x3f3f3f3f;
struct bian{
int next,to;
bian(){
next=0;
}
}e[N];
int n,m,dfn[N],low[N],num,head[N],totm,ans,anss[N],root;
void add(int s,int ed){
e[++totm].next=head[s];
e[totm].to=ed;
head[s]=totm;
}
void tarjan(int now,int fa){
dfn[now]=low[now]=++num;
int cnt=0;
for(int i=head[now];i;i=e[i].next){//访问
int k=e[i].to;
if(k==fa) continue;//遍历过了/kk
if(dfn[k]==0){//new point
tarjan(k,fa);//继续遍历
low[now]=min(low[now],low[k]);//更新，去最小值
if(low[k]>=dfn[now]){
//回不去了/kk
//cout<<now<<"-"<<k<<endl;
cnt++;
if(now!=root||cnt>1) anss[++ans]=now;
}
}else low[now]=min(low[now],dfn[k]);//更新。
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
fs(i,1,m,1){
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
}
//totm--;
fs(i,1,n,1){
if(dfn[i]==0){//还没被访问过
root=i;
tarjan(i,0);//遍历去~
}
}
sort(anss+1,anss+ans+1);
int ans2=unique(anss+1,anss+ans+1)-(anss+1);//去重
cout<<ans2<<'\n';
fs(i,1,ans2,1) cout<<anss[i]<<' ';
return 0;
}
```