題干：

It's almost summer time, and that means that it's almost summer construction time! This year, the good people who are in charge of the roads on the tropical island paradise of Remote Island would like to repair and upgrade the various roads that lead between the various tourist attractions on the island.

The roads themselves are also rather interesting. Due to the strange customs of the island, the roads are arranged so that they never meet at intersections, but rather pass over or under each other using bridges and tunnels. In this way, each road runs between two specific tourist attractions, so that the tourists do not become irreparably lost.

Unfortunately, given the nature of the repairs and upgrades needed on each road, when the construction company works on a particular road, it is unusable in either direction. This could cause a problem if it becomes impossible to travel between two tourist attractions, even if the construction company works on only one road at any particular time.

So, the Road Department of Remote Island has decided to call upon your consulting services to help remedy this problem. It has been decided that new roads will have to be built between the various attractions in such a way that in the final configuration, if any one road is undergoing construction, it would still be possible to travel between any two tourist attractions using the remaining roads. Your task is to find the minimum number of new roads necessary.

Input

The first line of input will consist of positive integers?n?and?r, separated by a space, where 3 ≤?n?≤ 1000 is the number of tourist attractions on the island, and 2 ≤?r?≤ 1000 is the number of roads. The tourist attractions are conveniently labelled from 1 to?n. Each of the following?r?lines will consist of two integers,?vand?w, separated by a space, indicating that a road exists between the attractions labelled?v?and?w. Note that you may travel in either direction down each road, and any pair of tourist attractions will have at most one road directly between them. Also, you are assured that in the current configuration, it is possible to travel between any two tourist attractions.

Output

One line, consisting of an integer, which gives the minimum number of roads that we need to add.

Sample Input

Sample Input 1 10 12 1 2 1 3 1 4 2 5 2 6 5 6 3 7 3 8 7 8 4 9 4 10 9 10Sample Input 2 3 3 1 2 2 3 1 3

Sample Output

Output for Sample Input 1 2Output for Sample Input 2 0

題目大意：

某個企業(yè)想把一個熱帶天堂島變成旅游勝地，島上有N個旅游景點(diǎn)，任意2個旅游景點(diǎn)之間有路徑連通（注意不一定是直接連通）。而為了給游客提供更方便的服務(wù)，該企業(yè)要求道路部門在某些道路增加一些設(shè)施。

道路部門每次只會選擇一條道路施工，在該條道路施工完畢前，其他道路依然可以通行。然而有道路部門正在施工的道路，在施工完畢前是禁止游客通行的。這就導(dǎo)致了在施工期間游客可能無法到達(dá)一些景點(diǎn)。

為了在施工期間所有旅游景點(diǎn)依然能夠正常對游客開放，該企業(yè)決定搭建一些臨時橋梁，使得不管道路部門選在哪條路進(jìn)行施工，游客都能夠到達(dá)所有旅游景點(diǎn)。給出當(dāng)下允許通行的R條道路，問該企業(yè)至少再搭建幾條臨時橋梁，才能使得游客無視道路部門的存在到達(dá)所有旅游景點(diǎn)？

一句話題意：給一個無向連通圖，至少添加幾條邊使得去掉圖中任意一條邊不改變圖的連通性（即使得它變?yōu)檫呺p連通圖）。

解題報告：（鏈接）

首先建立模型：

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

???????模型很簡單，正在施工的道路我們可以認(rèn)為那條邊被刪除了。那么一個圖G能夠在刪除任意一條邊后，仍然是連通的，當(dāng)且僅當(dāng)圖G至少為雙連通的。

???????PS：不要問我為什么不是3-連通、4-連通...人家題目問“至少添加幾條邊”好不...

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

???????那么如果圖G有多個【邊雙連通分量】呢？至少應(yīng)該添加多少條邊，才能使得任意兩個【邊雙連通分量】之間都是雙連通（也就是圖G是雙連通的）？

???????這個問題就是本題的問題。要解決這個問題：

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

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

2、??把每一個【邊雙連通分量】都看做一個點(diǎn)（即【縮點(diǎn)】）

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

以樣例1為例，樣例1得到的圖G為上左圖，

其中Low[4]=Low[9]=Low[10]

???????Low[3]=Low[7]=Low[8]

???????Low[2]=Low[5]=Low[6]

???????Low[1]獨(dú)自為政....

把Low值相同的點(diǎn)劃分為一類，每一類就是一個【邊雙連通分量】，也就是【縮點(diǎn)】了，不難發(fā)現(xiàn)，連接【縮點(diǎn)】之間的邊，都是圖G的橋，那么我們就得到了上右圖以縮點(diǎn)為結(jié)點(diǎn)，已橋?yàn)闃溥吽鶚?gòu)造成的樹。

3、??問題再次被轉(zhuǎn)化為“至少在縮點(diǎn)樹上增加多少條樹邊，使得這棵樹變?yōu)橐粋€雙連通圖”。

首先知道一條等式：

若要使得任意一棵樹，在增加若干條邊后，變成一個雙連通圖，那么

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

具體做法如下：

統(tǒng)計(jì)出樹中度為1的節(jié)點(diǎn)的個數(shù)，即為葉節(jié)點(diǎn)的個數(shù)，記為leaf。則至少在樹上添加(leaf+1)/2條邊，就能使樹達(dá)到邊二連通，所以至少添加的邊數(shù)就是(leaf+1)/2。具體方法為，首先把兩個最近公共祖先最遠(yuǎn)的兩個葉節(jié)點(diǎn)之間連接一條邊，這樣可以把這兩個點(diǎn)到祖先的路徑上所有點(diǎn)收縮到一起，因?yàn)橐粋€形成的環(huán)一定是雙連通的。然后再找兩個最近公共祖先最遠(yuǎn)的兩個葉節(jié)點(diǎn)，這樣一對一對找完，恰好是(leaf+1)/2次，把所有點(diǎn)收縮到了一起。

那么我們只需要 求縮點(diǎn)樹中中度數(shù)為1的結(jié)點(diǎn)數(shù)（即葉子數(shù)）有多少就可以了。

4、??求出所有縮點(diǎn)的度數(shù)的方法

兩兩枚舉圖G的直接連通的點(diǎn)，只要這兩個點(diǎn)不在同一個【縮點(diǎn)】中，那么它們各自所在的【縮點(diǎn)】的度數(shù)都+1。注意由于圖G時無向圖，這樣做會使得所有【縮點(diǎn)】的度數(shù)都是真實(shí)度數(shù)的2倍，必須除2后再判斷葉子。

---

?但是其實(shí)這個題解包括下面這個代碼都是錯誤的，因?yàn)椴荒芡ㄟ^看low值是否相等來判斷是否在一個bcc中。具體代碼應(yīng)該看POJ - 3177，里面解釋的比較詳細(xì)了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; vector<int> vv[MAX]; int n,m; int dfn[MAX],low[MAX],out[MAX]; int stk[MAX],index,clk,scc; void init() {for(int i = 1; i<=n; i++) {vv[i].clear();dfn[i]=low[i]=out[i]=0;}clk = index = scc = 0; } void tarjan(int x,int rt) {dfn[x] = low[x] = ++clk;int up = vv[x].size();for(int i = 0; i<up; i++) {int v = vv[x][i];if(v == rt) continue;if(dfn[v] == 0) {tarjan(v,x);low[x] = min(low[x],low[v]);}else low[x] = min(low[x],dfn[v]);} } int main() {while(~scanf("%d",&n)) {scanf("%d",&m);init();for(int u,v,i = 1; i<=m; i++) {scanf("%d%d",&u,&v);vv[u].pb(v);vv[v].pb(u);}for(int i = 1; i<=n; i++) {if(dfn[i] == 0) tarjan(i,-1);//因?yàn)轭}目保證是連通圖所以其實(shí)可以直接tarjan(1,-1)的 }for(int up,u = 1; u<=n; u++) {up = vv[u].size();for(int v,j = 0; j<up; j++) {v = vv[u][j];//圖G中Low值相同的兩個點(diǎn)必定在同一個邊雙連通分量(即同一個縮點(diǎn))中if(low[u] == low[v]) continue;//檢查i、j是否不在同一個縮點(diǎn)中out[low[u]]++;out[low[v]]++;//注意是對縮點(diǎn)操作，不是對原圖的點(diǎn)}}int ans = 0;//記錄總度數(shù)=1（葉子）的縮點(diǎn)for(int i = 1; i<=n; i++) {if(out[i] == 2) ans++;//由于是無向圖，因此每個縮點(diǎn)的度都重復(fù)計(jì)算了2次，因此度數(shù)==2才是葉子結(jié)點(diǎn)}printf("%d\n",(ans+1)/2);//將一棵樹連成一個邊雙連通分量至少需要添加的邊數(shù)=(葉子節(jié)點(diǎn)數(shù)+1)/2}return 0 ; }

?

這里注意理解一下LOW的意思，因?yàn)橛懻摰亩际菬o向圖，所以下面我們說的含義也都是在無向圖的基礎(chǔ)上討論的，定義上說，LOW[cur]代表：cur點(diǎn)可以向上回溯到的最早的一個點(diǎn)的DFN值。但是我想說，嚴(yán)格來講，應(yīng)該代表從另一條路徑上可以向上回溯到的最早的一個點(diǎn)的DFN值，這里另一條路徑就是代表不是dfs來的這條路徑，而是其他路徑。

總結(jié)

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

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