文章目錄

• 割點
• • 代碼
• 橋
• 點雙連通分量
• • 代碼
• 邊雙連通分量
• • 代碼

割點

和強連通分量十分相似
分為樹枝邊、前向邊和后向邊
注意！

if(x!=r&&low[to]>=dfn[x]) cut[x]=1;

這句判斷只能在樹枝邊出現
否則會因為前向邊的存在而出錯

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long int n,m; const int N=1e6+100; struct node{int to,nxt; }p[2*N]; int fi[N],cnt=-1; void addline(int x,int y){p[++cnt]=(node){y,fi[x]};fi[x]=cnt; }int r; int dfn[N],t,low[N],cut[N]; void tj(int x){dfn[x]=low[x]=++t;int num=0;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(!dfn[to]){ // printf("x=%d to=%d\n",x,to);tj(to);low[x]=min(low[x],low[to]);if(x!=r&&low[to]>=dfn[x]) cut[x]=1;num++;}low[x]=min(low[x],dfn[to]);}if(x==r&&num>1) cut[x]=1;return; } int main(){memset(fi,-1,sizeof(fi));scanf("%d%d",&n,&m);int a,b,c;for(int i=1;i<=m;i++){scanf("%d%d",&a,&b);addline(a,b);addline(b,a); }for(int i=1;i<=n;i++){r=i;if(!dfn[i]) tj(i);}int ans=0;for(int i=1;i<=n;i++){if(cut[i]){ans++;}}printf("%d\n",ans);for(int i=1;i<=n;i++){if(cut[i]){printf("%d ",i);}}return 0; }

橋

也是類似的tarjan求法
但是需要注意:

樹枝邊需要直接跳過

判斷的條件是$lo{w}_{to}<df{n}_x$（不帶等！！）

仔細想想都是有道理的
2.是因為子樹如果有連回x的邊那么當前邊也不是割邊
1.是為了2服務的

void tarjan(int x){dfn[x]=low[x]=++tim;for(int i=fi[x];~i;i=p[i].nxt){if(i==(from[x]^1)) continue;int to=p[i].to;//printf(" x=%d to=%d\n",x,to);if(!dfn[to]){from[to]=i;tarjan(to);low[x]=min(low[x],low[to]);if(low[to]>dfn[x]) ans++;}low[x]=min(low[x],dfn[to]);} }

點雙連通分量

定義：點連通度>1的極大子圖

考慮建一個棧
把所有的前向邊和樹枝邊壓入棧中
每次通過$df{n}_x<=lo{w}_{to}$，判斷x是隔點時，就把棧里$(u,v)$及上面的邊全部彈出，他們相連的點組成一個點雙連通分量
找分量的好方法：dfs！！

代碼

洛谷P3225

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=2e3+100; const double eps=1e-6; inline ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return f*x; } int n,m; int ans; struct node{int to,nxt,from; }p[N<<1]; int fi[N],cnt; inline void addline(int x,int y){//printf("%d->%d w=%d\n",x,y,w);p[++cnt]=(node){y,fi[x],x};fi[x]=cnt; } int dfn[N],low[N],zhan[N],tim,top,cut[N],r,tot; void tarjan(int x){dfn[x]=low[x]=++tim;zhan[++top]=x;int nm=0;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;//printf("x=%d to=%d\n",x,to);if(!dfn[to]){++nm;tarjan(to);if(low[to]>=dfn[x]){cut[x]=1;}low[x]=min(low[x],low[to]);}else low[x]=min(low[x],dfn[to]);}if(x==r) cut[x]=nm>1; } int num,Cut,tag[N],t; bool vis[N]; void dfs(int x){if(vis[x]||tag[x]==t) return;num++;//printf("x=%d\n",x);if(cut[x]){tag[x]=t;Cut++;return;}vis[x]=1;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;dfs(to);} } int main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifint o=0;while(1){memset(fi,-1,sizeof(fi));cnt=-1;memset(vis,0,sizeof(vis));memset(dfn,0,sizeof(dfn));tim=0;top=0;memset(cut,0,sizeof(cut));memset(tag,0,sizeof(tag));m=read();n=0;if(!m) return 0;for(int i=1;i<=m;i++){int x=read(),y=read();addline(x,y);addline(y,x);n=max(n,max(x,y));}tot=n;for(int i=1;i<=n;i++){r=i;if(!dfn[i]) tarjan(i);}ll nm=0,ans=1;for(int i=1;i<=n;i++){//printf("i=%d cut=%d\n",i,cut[i]);if(!vis[i]&&!cut[i]){num=0;Cut=0;t=i;dfs(i);printf("i=%d num=%d Cut=%d\n",i,num,Cut);if(Cut==0){nm+=2;ans*=num*(num-1)/2;}else if(Cut==1){nm++;ans*=(num-1);}}}printf("Case %d: %lld %lld\n",++o,nm,ans);} }

邊雙連通分量

定義：邊連通度>1的極大子圖

把橋求出后去掉
剩下的連通塊就是邊雙連通分量
加邊使圖邊雙連通的方法：把所有橋連回去，形成一個樹。設樹度數為1的點的數量為$x$
若x=1，不用加邊
否則，加邊數為$(x+1)/2$

代碼

洛谷P2860

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=5e5+100; const double eps=1e-6; inline ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return f*x; } int n,m; int ans; struct node{int to,nxt; }p[N<<1]; int fi[N],cnt; inline void addline(int x,int y){//printf("%d->%d w=%d\n",x,y,w);p[++cnt]=(node){y,fi[x]};fi[x]=cnt; } int low[N],dfn[N],tim,from[N],cut[N],du[N]; int fa[N]; inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]); } inline void merge(int x,int y){x=find(x),y=find(y);fa[x]=y;return; } void tarjan(int x){dfn[x]=low[x]=++tim;for(int i=fi[x];~i;i=p[i].nxt){//printf(" x=%d to=%d\n",x,p[i].to);if(i==(from[x]^1)) continue;int to=p[i].to;//printf(" x=%d to=%d\n",x,to);if(!dfn[to]){from[to]=i;tarjan(to);low[x]=min(low[x],low[to]);if(low[to]>dfn[x]){cut[i]=2;cut[i^1]=1;}}low[x]=min(low[x],dfn[to]);}//printf("x=%d dfn=%d low=%d\n",x,dfn[x],low[x]); } int main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifmemset(fi,-1,sizeof(fi));cnt=1;n=read();m=read();for(int i=1;i<=m;i++){int x=read(),y=read();addline(x,y);addline(y,x);}for(int i=1;i<=n;i++){if(!dfn[i]) tarjan(i);}for(int i=1;i<=n;i++){fa[i]=i;}for(int x=1;x<=n;x++){for(int i=fi[x];~i;i=p[i].nxt){if(cut[i]) continue;merge(x,p[i].to);}}for(int x=1;x<=n;x++){int xx=find(x);for(int i=fi[x];~i;i=p[i].nxt){if(cut[i]!=2) continue;int yy=find(p[i].to);du[xx]++;du[yy]++;}}for(int i=1;i<=n;i++){if(find(i)==i&&du[i]==1) ans++;}printf("%d\n",ans==1?0:(ans+1)/2); } /* 3 intercommunicational alkylbenzenesulfonate tetraiodophenolphthalein 0 */ 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的模板：割点、桥与双连通的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。