题目链接
Road Construction POJ - 3352
题意
某个企业想把一个热带天堂岛变成旅游胜地，岛上有N个旅游景点，任意2个旅游景点之间有路径连通（注意不一定是直接连通）。而为了给游客提供更方便的服务，该企业要求道路部门在某些道路增加一些设施。
道路部门每次只会选择一条道路施工，在该条道路施工完毕前，其他道路依然可以通行。然而有道路部门正在施工的道路，在施工完毕前是禁止游客通行的。这就导致了在施工期间游客可能无法到达一些景点。
为了在施工期间所有旅游景点依然能够正常对游客开放，该企业决定搭建一些临时桥梁，使得不管道路部门选在哪条路进行施工，游客都能够到达所有旅游景点。给出当下允许通行的R条道路，问该企业至少再搭建几条临时桥梁，才能使得游客无视道路部门的存在到达所有旅游景点？
分析
抽象成一个图论模型:给定一个连通图，求至少加多少条边使得图是一个边双连通图。
用tarjan算法求出边双连通分量，将边双连通分量缩点，形成一个树图。找出树图中度数为1的点，将其两两连边即可。
时间复杂度O（n+m）。
代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;const int maxn=5e3+100;
vector<int> g[maxn];
int n,m,par[maxn],du[maxn];
int dfn[maxn],low[maxn];
stack<int> sta;void tarjan(int u,int fa,int dep)
{dfn[u]=low[u]=dep;sta.push(u);for(int i=0;i<g[u].size();i++){int v=g[u][i];if(v==fa) continue;if(dfn[v])low[u]=min(low[u],dfn[v]);else{tarjan(v,u,dep+1);low[u]=min(low[u],low[v]);}}if(dfn[u]==low[u]){while(!sta.empty()){int tmp=sta.top();sta.pop();par[tmp]=u;if(tmp==u) break;}}
}
void solve()
{for(int i=1;i<=n;i++){for(int j=0;j<g[i].size();j++){int x=par[i];int y=par[g[i][j]];if(x!=y)du[x]++;}}int sum=0;for(int i=1;i<=n;i++)if(du[i]==1)sum++;printf("%d\n",(sum+1)/2);
}
int main()
{while(~scanf("%d%d",&n,&m)){memset(du,0,sizeof(du));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));for(int i=0;i<=n;i++) par[i]=i;for(int i=0;i<m;i++){int u,v;scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}tarjan(1,-1,1);solve();for(int i=0;i<=n;i++) g[i].clear();}return 0;
}
题干没有明确说明没有重边，所以理应去掉重边，但当时没有注意到，运气好AC了。