原题：Road Construction

原题大意

某个企业想把一个热带天堂岛变成旅游胜地，岛上有N个旅游景点，任意2个旅游景点之间有路径连通（注意不一定是直接连通）。而为了给游客提供更方便的服务，该企业要求道路部门在某些道路增加一些设施。
道路部门每次只会选择一条道路施工，在该条道路施工完毕前，其他道路依然可以通行。然而有道路部门正在施工的道路，在施工完毕前是禁止游客通行的。这就导致了在施工期间游客可能无法到达一些景点。
为了在施工期间所有旅游景点依然能够正常对游客开放，该企业决定搭建一些临时桥梁，使得不管道路部门选在哪条路进行施工，游客都能够到达所有旅游景点。给出当下允许通行的R条道路，问该企业至少再搭建几条临时桥梁，才能使得游客无视道路部门的存在到达所有旅游景点？

算法分析

http://blog.csdn.net/lyy289065406/article/details/6762370

程序代码

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
const int maxn = 1e5+5;
struct Edge
{
    int u, v;
    Edge(int _u, int _v){u = _u; v = _v;}
};
int dfs_clock, isbridge[maxn], pre[maxn], cnt, ind[maxn];
vector<int> G[maxn];
int dfs(int u, int fa){
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(!pre[v]){
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            if(lowv > pre[u]){          //和割顶>=有区别
                isbridge[u] = true;
                isbridge[v] = true;
            }
        }
        else if(pre[v] < pre[u] && v != fa){
            lowu = min(lowu, pre[v]);
        }
    }
    if(fa < 0 && child == 1) isbridge[u] = false;
    return lowu;
}
void dfs2(int u){
    pre[u] = cnt;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(!pre[v]){
            if(isbridge[v] == false || isbridge[u] == false){
                dfs2(v);
            }
        }
    }
}
void solve(int n){
    mem(pre,0);
    mem(isbridge,false);
    dfs_clock = 0;
    for(int i = 1; i <= n; i++)
        if(!pre[i]) dfs(i, -1);
    cnt = 0;
    mem(pre,0);
    for(int i = 1; i <= n; i++)
        if(!pre[i]) {++cnt;dfs2(i);}
    mem(ind,0);
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < G[i].size(); j++){
            if(pre[i] != pre[G[i][j]]){
                ind[pre[i]]++;
                ind[pre[G[i][j]]]++;
            }
        }
    int cnt2 = 0;
    for(int i = 1; i <= cnt; i++)
        if(ind[i]/2 == 1) cnt2++;
    cout << (cnt2 + 1)/2 << "\n";
}
int main()
{

    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    while(cin >> n >> m){
        for(int i = 0; i < maxn; i++) G[i].clear();
        int u, v;
        for(int i = 1; i <= m; i++){
            cin >> u >> v;
            G[u].pb(v);
            G[v].pb(u);
        }
        solve(n);
    }
    return 0;
}