无向图联通分量总结
点双联通分量
定义
点集中任意两点间具有点不重复的路径
删去 \(u , v\) 以外的某点后 \(u , v\) 之间仍然联通
割点
定义：删除该点后使得图中极大联通分量数量增加的点
特性：一个点从属于两个点双是该点成为割点的充要条件，且两个点双最多共用一个割点
割点的求解
对该图建立 \(dfs\) 树，经过的边称树边，否则称返祖边，维护两个数组 \(dfn_i\) 和 \(low_i\)，分别保存节点 \(i\) 的 \(dfs\) 序和通过返祖边能够返回到的最早位置，如果节点 \(u\) 的子节点无法通过返祖边返回到早于节点 \(u\) 的节点，则删除节点 \(u\) 后该图将不再联通，即 \(u\) 是割点
特别的，没有任何点可以返回根节点的上方，需统计其子节点数量判断
割点模板题
#include<iostream>
#include<set>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=2e4+5;
const int M=1e5+5;
int n,m,head[N],nxt[M<<1],to[M<<1],cnt=0,dfn[N],low[N],idx=0;
set<int>ans;
void add(int u,int v)
{to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
void Tarjan(int u,int fa)
{dfn[u]=low[u]=++idx;int son=0;for(int i=head[u];i;i=nxt[i]){int v=to[i];if(v==fa) continue;if(dfn[v])//u->v是一条返祖边low[u]=min(low[u],dfn[v]);//在求解割点时不能用low[v]更新low[u]，否则无法满足“点不重复的路径”else{son++;Tarjan(v,u);low[u]=min(low[u],low[v]);if(fa!=0&&low[v]>=dfn[u])//u的子节点无法通过返祖边返回比u更早的节点ans.insert(u);}}if(fa==0&&son>=2)//根节点是割点ans.insert(u);
}
int main()
{IOS;cin>>n>>m;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;add(u,v),add(v,u);}for(int i=1;i<=n;i++)if(!dfn[i]) Tarjan(i,0);//题目不保证联通cout<<ans.size()<<'\n';for(set<int>::iterator it=ans.begin();it!=ans.end();it++)cout<<*it<<' ';return 0;
}
点双联通分量的求解
由于是按照 \(dfs\) 序遍历，因此遇到割点时，只需要取出已经走过的点，用栈倒序存储
点双联通分量模板题
#include<iostream>
#include<stack>
#include<vector>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=5e5+5;
const int M=2e6+5;
int n,m,head[N],nxt[M<<1],to[M<<1],cnt=0,dfn[N],low[N],idx=0,bcccnt=0;
stack<int>stk;
vector<int>ans[N];
void add(int u,int v)
{to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
void Tarjan(int u,int fa)
{dfn[u]=low[u]=idx++;stk.push(u);for(int i=head[u];i;i=nxt[i]){int v=to[i];if(v==fa) continue;if(dfn[v]) low[u]=min(low[u],dfn[v]);else{Tarjan(v,u);low[u]=min(low[u],low[v]);if(low[v]>=dfn[u])//找到一个割点{bcccnt++;while(stk.top()!=v){ans[bcccnt].push_back(stk.top());stk.pop();}ans[bcccnt].push_back(v),stk.pop();ans[bcccnt].push_back(u);//割点可从属于多个点双，所以仍保留在栈内}}}if(fa==0&&!head[u])//孤立点也算一个点双ans[++bcccnt].push_back(u);
}
int main()
{IOS;cin>>n>>m;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;if(u!=v)//注意自环add(u,v),add(v,u);}for(int i=1;i<=n;i++)if(!dfn[i]) Tarjan(i,0);cout<<bcccnt<<'\n';for(int i=1;i<=bcccnt;i++){cout<<ans[i].size()<<' ';for(vector<int>::iterator it=ans[i].begin();it!=ans[i].end();it++)cout<<*it<<' ';cout<<'\n';}return 0;
}
边双联通分量
定义
点集中任意两点具有边不重复的路径
删去任意一条边后，该子图仍然联通
特性
一个点只可能从属于一个边双
割边
定义：删除该边后使得图中极大联通分量数量增加的边
割边的求解
内容大体和求解割点相同，区别在于：
-
对于返祖边 \(u->v\) ，可以使用 \(low_v\) 更新 \(low_u\) ，不会违背“边不重复”的原则
-
重边需单独考虑，\(u,v\) 之间有重边的情况下删去一条不影响二者间的联通性
割边模板题
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=155;
const int M=5005;
int n,m,head[N],nxt[M<<1],to[M<<1],cnt=0,dfn[N],low[N],idx=0;
vector<pair<int,int>>ans;
void add(int u,int v)
{to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
void Tarjan(int u,int fa)
{dfn[u]=low[u]=++idx;int cnt=0;for(int i=head[u];i;i=nxt[i]){int v=to[i];if(v==fa)//注意重边{cnt++;if(cnt==1) continue;}if(!dfn[v]) Tarjan(v,u),low[u]=min(low[u],low[v]);elselow[u]=min(low[u],low[v]);//区别if(low[v]>dfn[u])//注意此处不可取等，相等时删去u，v之间的连边没有影响ans.push_back({min(u,v),max(v,u)});}
}
bool cmp(pair<int,int>x,pair<int,int>y)
{if(x.first==y.first) return x.second<y.second;return x.first<y.first;
}
int main()
{IOS;cin>>n>>m;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;add(u,v),add(v,u);}Tarjan(1,0);sort(ans.begin(),ans.end(),cmp);for(vector<pair<int,int>>::iterator it=ans.begin();it!=ans.end();it++)cout<<(*it).first<<' '<<(*it).second<<'\n';return 0;
}