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
Output
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 10
Sample Input 2
3 3
1 2
2 3
1 3 Sample Output
Output for Sample Input 1
2
Output for Sample Input 2
0 首先建立模型：
給定一個連通的無向圖G，至少要添加幾條邊，才能使其變為雙連通圖。
模型很簡單，正在施工的道路我們可以認為那條邊被删除了。那麼一個圖G能夠在删除任意一條邊後，仍然是連通的，當且僅當圖G至少為雙連通的。
PS：不要問我為什麼不是3-連通、4-連通...人家題目問“至少添加幾條邊”好不...
顯然，當圖G存在橋（割邊）的時候，它必定不是雙連通的。橋的兩個端點必定分别屬于圖G的兩個【邊雙連通分量】（注意不是點雙連通分量），一旦删除了橋，這兩個【邊雙連通分量】必定斷開，圖G就不連通了。但是如果在兩個【邊雙連通分量】之間再添加一條邊，橋就不再是橋了，這兩個【邊雙連通分量】之間也就是雙連通了。
那麼如果圖G有多個【邊雙連通分量】呢？至少應該添加多少條邊，才能使得任意兩個【邊雙連通分量】之間都是雙連通（也就是圖G是雙連通的）？
這個問題就是本題的問題。要解決這個問題：
1、 首先要找出圖G的所有【邊雙連通分量】。
Tarjan算法用來尋找圖G的所有【邊雙連通分量】是最簡單有效的方法，因為Tarjan算法在DFS過程中會對圖G所有的結點都生成一個Low值，而由于題目已表明任意兩個結點之間不會出現重邊，是以Low值相同的兩個結點必定在同一個【邊雙連通分量】中！ （如果是有重邊的話，那麼不同的low值是可能是屬于同一個邊雙連通分量的，這個時候就要通過其他方法去求解邊雙連通分量。不過這不是本題要讨論的）
2、 把每一個【邊雙連通分量】都看做一個點（即【縮點】）
也有人稱【縮點】為【塊】，都是一樣的。其實縮點不是真的縮點，隻要利用Low值對圖G的點分類處理，就已經縮點了。
以樣例1為例，樣例1得到的圖G為上左圖，
其中Low[4]=Low[9]=Low[10]
Low[3]=Low[7]=Low[8]
Low[2]=Low[5]=Low[6]
Low[1]獨自為政....
把Low值相同的點劃分為一類，每一類就是一個【邊雙連通分量】，也就是【縮點】了，不難發現，連接配接【縮點】之間的邊，都是圖G的橋，那麼我們就得到了上右圖以縮點為結點，已橋為樹邊所構造成的樹。
3、 問題再次被轉化為“至少在縮點樹上增加多少條樹邊，使得這棵樹變為一個雙連通圖”。
首先知道一條等式：
若要使得任意一棵樹，在增加若幹條邊後，變成一個雙連通圖，那麼
至少增加的邊數 =（ 這棵樹總度數為1的結點數 + 1 ）/ 2
（證明就不證明了，自己畫幾棵樹比劃一下就知道了）
那麼我們隻需求縮點樹中總度數為1的結點數（即葉子數）有多少就可以了。換而言之，我們隻需求出所有縮點的度數，然後判斷度數為1的縮點有幾個，問題就解決了。
4、 求出所有縮點的度數的方法
兩兩枚舉圖G的直接連通的點，隻要這兩個點不在同一個【縮點】中，那麼它們各自所在的【縮點】的度數都+1。注意由于圖G時無向圖，這樣做會使得所有【縮點】的度數都是真實度數的2倍，必須除2後再判斷葉子。
[點連通度與邊連通度]
在一個無向連通圖中，如果有一個頂點集合，删除這個頂點集合，以及這個集合中所有頂點相關聯的邊以後，原圖變成多個連通塊，就稱這個點集為割點集合。一個圖的點連通度的定義為，最小割點集合中的頂點數。
類似的，如果有一個邊集合，删除這個邊集合以後，原圖變成多個連通塊，就稱這個點集為割邊集合。一個圖的邊連通度的定義為，最小割邊集合中的邊數。
[雙連通圖、割點與橋]
如果一個無向連通圖的點連通度大于1，則稱該圖是點雙連通的(point biconnected)，簡稱雙連通或重連通。一個圖有割點，當且僅當這個圖的點連通度為1，則割點集合的唯一進制素被稱為割點(cut point)，又叫關節點(articulation point)。
如果一個無向連通圖的邊連通度大于1，則稱該圖是邊雙連通的(edge biconnected)，簡稱雙連通或重連通。一個圖有橋，當且僅當這個圖的邊連通度為1，則割邊集合的唯一進制素被稱為橋(bridge)，又叫關節邊(articulation edge)。
可以看出，點雙連通與邊雙連通都可以簡稱為雙連通，它們之間是有着某種聯系的，下文中提到的雙連通，均既可指點雙連通，又可指邊雙連通。
[雙連通分支]
在圖G的所有子圖G'中，如果G'是雙連通的，則稱G'為雙連通子圖。如果一個雙連通子圖G'它不是任何一個雙連通子圖的真子集，則G'為極大雙連通子圖。雙連通分支(biconnected component)，或重連通分支，就是圖的極大雙連通子圖。特殊的，點雙連通分支又叫做塊。[求割點與橋]
該算法是R.Tarjan發明的。對圖深度優先搜尋，定義DFS(u)為u在搜尋樹（以下簡稱為樹）中被周遊到的次序号。定義Low(u)為u或u的子樹中能通過非父子邊追溯到的最早的節點，即DFS序号最小的節點。根據定義，則有：
Low(u)=Min { DFS(u) DFS(v) (u,v)為後向邊(返祖邊) 等價于 DFS(v)<DFS(u)且v不為u的父親節點 Low(v) (u,v)為樹枝邊(父子邊) }
一個頂點u是割點，當且僅當滿足(1)或(2) (1) u為樹根，且u有多于一個子樹。 (2) u不為樹根，且滿足存在(u,v)為樹枝邊(或稱父子邊，即u為v在搜尋樹中的父親)，使得DFS(u)<=Low(v)。
一條無向邊(u,v)是橋，當且僅當(u,v)為樹枝邊，且滿足DFS(u)<Low(v)。
[求雙連通分支]
下面要分開讨論點雙連通分支與邊雙連通分支的求法。
對于點雙連通分支，實際上在求割點的過程中就能順便把每個點雙連通分支求出。建立一個棧，存儲目前雙連通分支，在搜尋圖時，每找到一條樹枝邊或後向邊(非橫叉邊)，就把這條邊加入棧中。如果遇到某時滿足DFS(u)<=Low(v)，說明u是一個割點，同時把邊從棧頂一個個取出，直到遇到了邊(u,v)，取出的這些邊與其關聯的點，組成一個點雙連通分支。割點可以屬于多個點雙連通分支，其餘點和每條邊隻屬于且屬于一個點雙連通分支。
對于邊雙連通分支，求法更為簡單。隻需在求出所有的橋以後，把橋邊删除，原圖變成了多個連通塊，則每個連通塊就是一個邊雙連通分支。橋不屬于任何一個邊雙連通分支，其餘的邊和每個頂點都屬于且隻屬于一個邊雙連通分支。
[構造雙連通圖]
一個有橋的連通圖，如何把它通過加邊變成邊雙連通圖？方法為首先求出所有的橋，然後删除這些橋邊，剩下的每個連通塊都是一個雙連通子圖。把每個雙連通子圖收縮為一個頂點，再把橋邊加回來，最後的這個圖一定是一棵樹，邊連通度為1。
統計出樹中度為1的節點的個數，即為葉節點的個數，記為leaf。則至少在樹上添加(leaf+1)/2條邊，就能使樹達到邊二連通，是以至少添加的邊數就是(leaf+1)/2。具體方法為，首先把兩個最近公共祖先最遠的兩個葉節點之間連接配接一條邊，這樣可以把這兩個點到祖先的路徑上所有點收縮到一起，因為一個形成的環一定是雙連通的。然後再找兩個最近公共祖先最遠的兩個葉節點，這樣一對一對找完，恰好是(leaf+1)/2次，把所有點收縮到了一起。
以上是介紹。這道題的核心是求該圖的縮點樹至少添加幾條邊，才可以讓它成為雙聯通圖。由上知，(leaf+1)/2可得。
題意：一個連通的無向圖，求至少需要添加幾條邊，救能保證删除任意一條邊，圖仍然是連通的。
思路：邊的雙連通圖。其實就是要求至少添加幾條邊，可以使整個圖成為一個邊雙連通圖。用tarjan算法(求割點割邊)求出low數組，這裡可以簡化，然 後依據“low相同的點在一個邊連通分量中”，縮點之後構造成樹(這裡可以直接利用low[]數組，low[i]即為第i節點所在的連通分量的标号)。求 出樹中出度為1的節點數left，答案即為(leaf+1)/2。
代碼：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int N = 5000;
int vis[N], head[N], w[1010][1010], low[N], degree[N];
struct node
{
int to, next1;
} p[2*N+100];
int cnt, num;
void add(int u,int v)
{
p[cnt].to=v,p[cnt].next1=head[u];
head[u]=cnt++;
return ;
}
void dfs(int u,int fa)
{
vis[u]=1, low[u]=num++;
for(int i=head[u]; i!=-1; i=p[i].next1)
{
int v=p[i].to;
if(v==fa) continue;
if(!vis[v]) dfs(v,u);
low[u]=min(low[u],low[v]);
}
return ;
}
int tarjan(int n)
{
memset(vis,0,sizeof(vis));
memset(low,0,sizeof(low));
memset(degree,0,sizeof(degree));
num=0;
dfs(1,-1);
for(int i=1; i<=n; i++)
{
for(int j=head[i]; j!=-1; j=p[j].next1)
{
int u=p[j].to;
if(low[u]!=low[i]) degree[low[i]]++;
}
}
int sum=0;
for(int i=1; i<=n; i++)
if(degree[i]==1)sum++;
return (sum+1)/2;
}
int main()
{
int n, m,x, y;
scanf("%d %d", &n, &m);
memset(head,-1,sizeof(head));
memset(w,0,sizeof(w));
for(int i=0; i<m; i++)
{
scanf("%d %d", &x, &y);
if(w[x][y]) continue;
w[x][y]=w[y][x]=1;
add(x,y); add(y,x);
}
printf("%d\n",tarjan(n));
return 0;
}
![SCC算法求強連通分量簡單講解證明及實作強連通分量SCC算法簡介兩個概念SCC算法僞代碼描述SCC算法正确性證明代碼實作[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)