题目地址：http://poj.org/problem?id=3352
题意：给你一个图，要求你加入最少的边，使得最后得到的图为一个边双连通分支。所谓的边双连通分支，即不存在桥的连通分支。
思路：
可以求出所有的桥，把桥删掉。然后把所有的连通分支求出来，显然这些连通分支就是原图中的双连通分支。把它们缩成点，然后添上刚才删去的桥，就构成了一棵树。在树上添边使得树变成一个双连通分支即可。
本题只要求输出一共需要添加多少条边，而不需要求具体的方案。其实可以统计度为1的叶子节点（共有x个），然后直接输出(x+1)/2即可
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10000+10;
typedef pair<int,int> Edge;
int index=0,ncolor;
vector<bool> vis(maxn);
vector<int> dfn(maxn),low(maxn),st,ID(maxn);
vector<vector<int> > G(maxn),color(maxn);
vector<Edge> bridge;
void Tarjan(int u,int father)
{dfn[u]=low[u]=++index;vis[u]=true;for(int i=0;i<G[u].size();i++){int v=G[u][i];if(!vis[v]){Tarjan(v,u);low[u]=min(low[u],low[v]);if(dfn[u]<low[v]) bridge.push_back(Edge(u,v));}else if(father!=v) //只能由非父子边更新 low[u]=min(low[u],dfn[v]);}
}
void Tarjan2(int u) //染色
{dfn[u]=low[u]=++index;vis[u]=true;st.push_back(u);for(int i=0;i<G[u].size();i++){int v=G[u][i];if(!vis[v]){Tarjan2(v);low[u]=min(low[u],low[v]);}else if(find(st.begin(),st.end(),v)!=st.end()) //in stacklow[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){int v; ncolor++;do{v=st.back(); st.pop_back();color[ncolor].push_back(v);ID[v]=ncolor;}while(v!=u);}
}
void getGraph(int n){index=ncolor=0;fill(vis.begin(),vis.begin()+n+1,false);for(int i=1;i<=n;i++)if(!vis[i]) Tarjan2(i);
}
int solve(int n)
{int m=0,ans; //m标记出度为1的点有几个 vector<int> points;for(int i=1;i<=ncolor;i++) {points.clear();for(int j=0;j<color[i].size()&&points.size()<=1;j++){int u=color[i][j];for(int k=0;k<G[u].size()&&points.size()<=1;k++){int v=G[u][k];if(ID[u]!=ID[v]&&find(points.begin(),points.end(),v)==points.end()) //有出度 points.push_back(v);}}if(points.size()==1) m++;}return m;
}
int main()
{int n,m;cin>>n>>m;while(m--){int u,v;cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}index=0;Tarjan(1,0); for(int i=0;i<bridge.size();i++){ //删去 int u=bridge[i].first,v=bridge[i].second;for(int j=0;j<G[u].size();j++){if(G[u][j]==v) G[u].erase(G[u].begin()+j);}for(int j=0;j<G[v].size();j++){if(G[v][j]==u) G[v].erase(G[v].begin()+j);}}getGraph(n); //染色 ，缩点 for(int i=0;i<bridge.size();i++){ //加上桥边 G[bridge[i].first].push_back(bridge[i].second);G[bridge[i].second].push_back(bridge[i].first);}cout<<(solve(n)+1)/2<<endl;return 0;
}