poj3177 BZOJ1718 Redundant Paths

Description：

有F个牧场，1<=F<=5000，现在一个牧群经常需要从一个牧场迁移到另一个牧场。奶牛们已经厌烦老是走同一条路，所以有必要再新修几条路，这样它们从一个牧场迁移到另一个牧场时总是可以选择至少两条独立的路。现在F个牧场的任何两个牧场之间已经至少有一条路了，奶牛们需要至少有两条。
给定现有的R条直接连接两个牧场的路，F-1<=R<=10000，计算至少需要新修多少条直接连接两个牧场的路，使得任何两个牧场之间至少有两条独立的路。两条独立的路是指没有公共边的路，但可以经过同一个中间顶点

思路：双联通分量缩点，然后将缩成的树的叶子节点连起来就可以把得到一个双联通图，叶子节点为入度为1的点

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e4 + 10;

int head[N], now = 1;
struct edges{
    int to, next;
}edge[N<<1];
void add(int u, int v){ edge[++now] = {v, head[u]}; head[u] = now;}

int n, m, dfn[N], cnt, tot, bri[N<<1], vis[N], low[N], dict[N], num, deg[N];
struct input{
    int x, y;
}in[N];

void tarjan(int x, int in_edge){
    dfn[x] = low[x] = ++cnt;
    for(int i = head[x]; i; i = edge[i].next){
        int v = edge[i].to;
        if(!dfn[v]){
            tarjan(v, i);
            low[x] = min(low[x], low[v]);
            if(low[v] > dfn[x]) bri[i] = bri[i ^ 1] = 1;
        }
        else if(i != (in_edge ^ 1)) low[x] = min(low[x], dfn[v]);
    }
}

void dfs(int x){
    dict[x] = tot; vis[x] = 1;
    for(int i = head[x]; i; i = edge[i].next){
        int v = edge[i].to;
        if(vis[v] || bri[i]) continue;
        dfs(v); 
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int x, y;
    for(int i = 1; i <= m; i++){
        cin>>x>>y;
        in[i] = {x, y};
        add(x, y); add(y, x);
    }
    for(int i = 1; i <= n; i++)
      if(!dfn[i]) tarjan(i, 0);
    for(int i = 1; i <= n; i++)
      if(!vis[i]) tot++, dfs(i);
    for(int i = 1; i <= m; i++){
        if(dict[in[i].x] == dict[in[i].y]) continue;
        deg[dict[in[i].x]]++, deg[dict[in[i].y]]++;
    }
    for(int i = 1; i <= tot; i++)
      if(deg[i] == 1) num++;
    cout<<(num + 1) / 2 << endl;
    return 0;
}