對于一個有橋的連通圖，加邊變成邊雙連通圖

1.求出所有的橋，然后刪除這些橋邊。剩下的每個連通塊都是一個雙連通子圖。

2.把每個雙連通子圖收縮為一個頂點。

3.加回橋邊，統計度為1的節點的個數（葉節點的個數），記為 leaf

則：至少在樹上加?(leaf+1)/2 條邊，就能使樹達到邊雙連通

除使用兩次 dfs 外，還可以使用 Tarjan 算法一次求出所有點的 low[i] 值，由于同一個邊雙連通分量的點他們的 low[i] 值一定相同，因此對于不同邊雙連通分量的點，他們的 low 值一定不同。

int n,m; int dfn[N],low[N]; int degree[N]; int block_cnt; vector<int> G[N]; int Tarjan(int x,int father) {int lowx=dfn[x]=++block_cnt;for(int i=0; i<G[x].size(); i++) {int y=G[x][i];if(y==father)continue;if(dfn[y]==0) {int lowy=Tarjan(y,x);lowx=min(lowx,lowy);} else if(dfn[y]<dfn[x])lowx=min(lowx,dfn[y]);}return low[x]=lowx; } int main() {scanf("%d%d",&n,&m);block_cnt=0;memset(dfn,0,sizeof(dfn));memset(degree,0,sizeof(degree));for(int i=0; i<n; i++)G[i].clear();for(int i=1; i<=m; i++) {int x,y;scanf("%d%d",&x,&y);G[x].push_back(y);G[y].push_back(x);}Tarjan(1,-1);//求所有點的low值for(int x=1; x<=n; x++) { //遍歷每條邊for(int i=0; i<G[x].size(); i++) {int y=G[x][i];if(low[x]!=low[y])//每個不同的low值代表一個邊雙連通分量degree[low[y]]++;}}int cnt=0;for(int i=1; i<=n; i++)if(degree[i]==1)cnt++;printf("%d\n",(cnt+1)/2);//加邊條數/** 邊雙連通分量個數* int cnt=0;* for(int i=1;i<=n;i++)* if(degree[i]>0)* cnt++;* printf("%d\n",cnt);*/return 0; }

總結

以上是生活随笔為你收集整理的图论 —— 图的连通性 —— 有桥连通图加边变边双连通图的全部內容，希望文章能夠幫你解決所遇到的問題。

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