?題意：給定一個連通的無向圖G，至少要添加幾條邊，才能使其變?yōu)殡p連通圖。

解題思路：

顯然，當圖G存在橋（割邊）的時候，它必定不是雙連通的。橋的兩個端點必定分別屬于圖G的兩個【邊雙連通分量】（注意不是點雙連通分量），一旦刪除了橋，這兩個【邊雙連通分量】必定斷開，圖G就不連通了。但是如果在兩個【邊雙連通分量】之間再添加一條邊，橋就不再是橋了，這兩個【邊雙連通分量】之間也就是雙連通了。

?

首先要找出圖G的所有【邊雙連通分量】。

Tarjan算法用來尋找圖G的所有【邊雙連通分量】是最簡單有效的方法，因為Tarjan算法在DFS過程中會對圖G所有的結(jié)點都生成一個Low值，而由于題目已表明任意兩個結(jié)點之間不會出現(xiàn)重邊，因此Low值相同的兩個結(jié)點必定在同一個【邊雙連通分量】中！? （如果是有重邊的話，那么不同的low值是可能是屬于同一個邊雙連通分量的，這個時候就要通過其他方法去求解邊雙連通分量。不過這不是本題要討論的）

?

把每一個【邊雙連通分量】都看做一個點（即【縮點】）

也有人稱【縮點】為【塊】，都是一樣的。其實縮點不是真的縮點，只要利用Low值對圖G的點分類處理，就已經(jīng)縮點了。

至少增加的邊數(shù) =（ 這棵樹總度數(shù)為1的結(jié)點數(shù) + 1 ）/ 2

這個證明可以數(shù)學(xué)歸納法簡單證明。

參考博客：http://blog.csdn.net/lyy289065406/article/details/6762370

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 1005; struct Edge {int from,to,next;bool cut; }edge[maxn<<1]; int n,m,cnt,head[maxn]; int top,Index,block,Stack[maxn],ind[maxn]; int bel[maxn],low[maxn],dfsn[maxn]; bool Instack[maxn];void init() {cnt = top = Index = block = 0;memset(head,-1,sizeof(head));memset(dfsn,0,sizeof(dfsn));memset(ind,0,sizeof(ind));memset(Instack,false,sizeof(Instack)); }void addedge(int u,int v) {edge[cnt].to = v;edge[cnt].from = u;edge[cnt].cut = false;edge[cnt].next = head[u];head[u] = cnt++; }void Tarjan(int u,int fa) {low[u] = dfsn[u] = ++Index;Stack[top++] = u;Instack[u] = true;for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if(v == fa) continue;if(dfsn[v] == 0){Tarjan(v,u);if(low[v] < low[u])low[u] = low[v];if(low[v] > dfsn[u]){edge[i].cut = true;edge[i^1].cut = true;}}else if(Instack[v] && low[u] > dfsn[v])low[u] = dfsn[v];}if(low[u] == dfsn[u]){int v;block++;do{v = Stack[--top]; bel[v] = block;Instack[v] = false; }while(v != u);} }int main() {int u,v;while(scanf("%d%d",&n,&m)!=EOF){init();for(int i = 1; i <= m; i++){scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);}for(int i = 1; i <= n; i++)if(!dfsn[i])Tarjan(i,-1);for(int i = 0; i < 2*m; i += 2){u = edge[i].from, v = edge[i].to;if(bel[u] != bel[v])ind[bel[u]]++,ind[bel[v]]++;}int leaf = 0;for(int i = 1; i <= block; i++)if(ind[i] == 1)leaf++;printf("%d\n",(leaf+1)/2);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的poj 3352 Road Construction(边-双连通分量)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。