http://poj.org/problem?id=3352
题意：简化一下原题题意，意思就是给定一个连通图，问至少要加入几条边使得整个图变成一个边连通图，即图中任意两点都有两条以上的路径（不一定直接相连）。
思路：tarjan算法，设置一个low数组，在建立深搜树的过程中，我们会得到每个节点的low值，对于low值相等的节点在同一个双连通分量中。由于在同一个边连通分量中的点的“地位”是相同的，因此可以将这些双连通分量缩点，就形成一颗无根树。
要让这个无根树变成一个双连通分量，我们需要计算无根树种度为1的节点数平p, 那么答案就是(p+1)/2;
poj3177与这个题类似，不过这个题中没有重边，在3177中，只需加上判重边就可以了。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
const int maxn = 5005;
bool map[maxn][maxn];
vector <int> edge[maxn];
int n,m;
int dfn[maxn],low[maxn],instack[maxn],dep;
void tarjan(int u, int fa)
{
dfn[u] = low[u] = ++dep;
instack[u] = 1;
for(int i = 0; i < (int)edge[u].size(); i++)
{
int v = edge[u][i];
if(v == fa) continue;
if(!dfn[v])
{
tarjan(v,u);
low[u] = min(low[u],low[v]);
}
else if(instack[v])
low[u] = min(low[u],dfn[v]);
}
}
int main()
{
scanf("%d %d",&n,&m);
memset(map,false,sizeof(map));
for(int i = 0; i <= n; i++)
edge[i].clear();
int u,v;
for(int i = 0; i < m; i++)
{
scanf("%d %d",&u,&v);
if(!map[u][v])
{
edge[u].push_back(v);
edge[v].push_back(u);
map[u][v] = map[v][u] = 1;
}
}
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(instack,0,sizeof(instack));
dep = 0;
tarjan(1,-1);
int leaf[maxn];
memset(leaf,0,sizeof(leaf));
for(int u = 1; u <= n; u++)
{
for(int i = 0; i < (int)edge[u].size(); i++)
{
int v = edge[u][i];
if(low[u] != low[v])
leaf[ low[u] ] ++;
}
}
int cnt = 0;
for(int i = 1; i <= n; i++)
{
if(leaf[i] ==1)
cnt++;
}
printf("%d\n",(cnt+1)/2);
return 0;
}