連通分量
個數可以通過一次BFS或者DFS得到
割點和橋
可以枚舉刪除每一個點或者每一條邊，判斷連通分量個數是否增加
更好的方法
?
該算法是R.Tarjan發明的。對圖深度優先搜索，定義DFS(u)為u在搜索樹（以下簡稱為樹）中被遍歷到的次序號。定義Low(u)為u或u的子樹中能通過非父子邊追溯到的最早的節點，即DFS序號最小的節點。
一個頂點u是割點，當且僅當滿足(1)或(2)?
(1) u為樹根，且u有多于一個子樹。?
(2) u不為樹根，且滿足存在(u,v)為樹枝邊(或稱父子邊，即u為v在搜索樹中的父親)，使得DFS(u)<=Low(v)。
一條無向邊(u,v)是橋，當且僅當(u,v)為樹枝邊，且滿足DFS(u)<Low(v)。
void dfs(int u,int fa)
{int child=0;pre[u]=low[u]=++tim;for(int e=fst[u];e!=-1;e=nxt[e]){int v=s[e].y;if(!pre[v]){child++;dfs(v,u);low[u]=min(low[u],low[v]);if(low[v]>=pre[u])cut[u]++;if(low[v]>pre[u])bridge[e]=1;}elseif(pre[v]<pre[u] && v!=fa) //v!=falow[u]=min(low[u],pre[v]);}if(fa<0&&child==1)cut[u]=0;
}
需要注意的是：
1.如果i是root，那么去掉i后，連通分量個數增加cut[i]-1個。如果i不是root，那么連通分量增加cut[i]個
2.無向圖 ?bridge[e]=1 ?bridge[e+1]同樣應標注為1(bridge[e-1])
雙連通
?
雙連通分點雙聯通和邊雙聯通
對于一個連通圖，若任意兩點至少存在兩條“點不重復”的路徑，則此連通圖是點-雙連通的，意味著任意的兩條邊都是在同一個簡單環上，即內部無割頂。點-雙連通的極大子圖叫做雙連通分量或塊。定理：不同雙聯通分量最多只有一個公共點，且它一定是割頂，任意割頂都是至少兩個不同雙連通分量的公共點。
對于一個連通圖，若任意兩點至少存在兩條“邊不重復”的路徑，則此連通圖是邊-雙連通的，意味著只需要每條邊都至少在一個簡單環中，即所有邊都不是橋。邊-雙連通的極大子圖叫做邊-雙連通分量，除了橋不屬于任何邊-雙連通分量之外，其他每條邊恰好屬于一個邊-雙連通分量，而且把所有橋刪除之后，每個連通分量對應原圖中的一個邊-雙連通分量。
對于點雙連通分支，實際上在求割點的過程中就能順便把每個點雙連通分支求出。建立一個棧，存儲當前雙連通分支，在搜索圖時，每找到一條樹枝邊或后向邊(非橫叉邊)，就把這條邊加入棧中。如果遇到某時滿足DFS(u)<=Low(v)，說明u是一個割點，同時把邊從棧頂一個個取出，直到遇到了邊(u,v)，取出的這些邊與其關聯的點，組成一個點雙連通分支。割點可以屬于多個點雙連通分支，其余點和每條邊只屬于且屬于一個點雙連通分支。
對于邊雙連通分支，求法更為簡單。只需在求出所有的橋以后，把橋邊刪除，原圖變成了多個連通塊，則每個連通塊就是一個邊雙連通分支。橋不屬于任何一個邊雙連通分支，其余的邊和每個頂點都屬于且只屬于一個邊雙連通分支。
有重邊的 邊-雙連通分量 應尤其注意，因為重邊也算不同的邊。解決方案是用邊判斷，而不是利用v!=fa判斷能否由pre[v]更新low[u]
void dfs(int u,int fa)
{tim++;low[u]=pre[u]=tim;for(int e=fst[u];e!=-1;e=nxt[e]){int w=e;if (e%2)w++;else w--;int v=s[e].y;if(!pre[v]){dfs(v,e);low[u]=min(low[u],low[v]);if (low[v]>pre[u])bridge[e]=bridge[w]=1;}else//if(pre[v]<pre[u] && v != fa)if (pre[v]<pre[u] && (e!=fa && w!=fa))low[u]=min(low[u],pre[v]);}
}?
void dfs(int u)
{tim++;pre[u]=low[u]=tim;for(int e=fst[u];e!=-1;e=nxt[e]){int w=e;if(w%2)w++;else w--;int v=s[e].y;if(!pre[v]){flag[e]=flag[w]=1;dfs(v);low[u]=min(low[u],low[v]);if(low[v]>pre[u])cnt[e]=cnt[w]=1;}else if(pre[v]<pre[u]&&!flag[e]) //判斷邊而不是判斷點 {flag[e]=flag[w]=1;low[u]=min(low[u],pre[v]);}}
}構造雙連通圖
?
一個有橋的連通圖，如何把它通過加邊變成邊雙連通圖？方法為首先求出所有的橋，然后刪除這些橋邊，剩下的每個連通塊都是一個雙連通子圖。把每個雙連通子圖收縮為一個頂點，再把橋邊加回來，最后的這個圖一定是一棵樹，邊連通度為1。
統計出樹中度為1的節點的個數，即為葉節點的個數，記為leaf。則至少在樹上添加(leaf+1)/2條邊，就能使樹達到邊二連通，所以至少添加的邊數就是(leaf+1)/2。具體方法為，首先把兩個最近公共祖先最遠的兩個葉節點之間連接一條邊，這樣可以把這兩個點到祖先的路徑上所有點收縮到一起，因為一個形成的環一定是雙連通的。然后再找兩個最近公共祖先最遠的兩個葉節點，這樣一對一對找完，恰好是(leaf+1)/2次，把所有點收縮到了一起。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int m,tn,n;
struct path{int x,y;}s[20001];
int fst[20001],nxt[20001];
bool bridge[20001];
int pre[5001],low[5001];
int tim,part,x,y;
int hash[5001],out[5001];void dfs(int u,int fa)
{tim++;low[u]=pre[u]=tim;for(int e=fst[u];e!=-1;e=nxt[e]){int w=e;if (e%2)w++;else w--;int v=s[e].y;if(!pre[v]){dfs(v,e);low[u]=min(low[u],low[v]);if (low[v]>pre[u])bridge[e]=bridge[w]=1;}else//if(pre[v]<pre[u] && v != fa)if (pre[v]<pre[u] && (e!=fa && w!=fa))low[u]=min(low[u],pre[v]);}
}void makeside(int x,int y)
{n++;s[n].x=x;s[n].y=y;nxt[n]=fst[x];fst[x]=n;
}void color(int i)
{hash[i]=part;for(int e=fst[i];e!=-1;e=nxt[e])if (!bridge[e]&&!hash[s[e].y])color(s[e].y);
}void print()
{int z=0;for(int e=1;e<=n;e++)if(bridge[e]){out[hash[s[e].x]]++;out[hash[s[e].y]]++;}for(int i=1;i<=part;i++)if(out[i]==2)z++;cout<<(z+1)/2<<endl;
}int main()
{while(scanf("%d%d",&m,&tn)==2){memset(fst,-1,sizeof(fst));memset(nxt,-1,sizeof(nxt));memset(bridge,0,sizeof(bridge));memset(hash,0,sizeof(hash));memset(out,0,sizeof(out));memset(pre,0,sizeof(pre));memset(low,0,sizeof(low));n=part=tim=0;for(int i=1;i<=tn;i++){scanf("%d%d",&x,&y);makeside(x,y);makeside(y,x);}for(int i=1;i<=m;i++)if(!pre[i])dfs(i,-1);for(int i=1;i<=m;i++)if(!hash[i]){part++;color(i);}print();} return 0;
}
見題目：
HOJ
1007 SPF
1098 NetWork
1789 Electricity
2360 Redundant Paths
?
POJ
3117?Redundant Paths
3352?Road Construction
參考：
https://www.byvoid.com/blog/biconnect
http://blog.csdn.net/z635457712a/article/details/8229113
http://blog.csdn.net/lyy289065406/article/details/6762370
?
