https://vjudge.net/problem/POJ-3177#author=haomie
思路：本质上就是用求边双连通分量的思路来求解；
首先我们可以对图进行边连通分量缩点， 缩点后图就会变成一颗树， 代表任意2点之间的路径是唯一的。 这时候题目转化为添加最少的边使任意2点的路径至少有2条。
结论： 对有n个入度为1的点的树，至少需要 (n + 1) / 2 的边使其变成一个边连通分量。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=5005,M=10005;
int head[N],ver[M<<1],Next[M<<1];
int dfn[N],low[N],n,m,tot,num;
bool bridge[M<<1];
int c[N],in[N],dcc;
long long ans=0;
void add(int x,int y){
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void dfs(int x){
    c[x]=dcc;
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i];
        if(c[y]||bridge[i])    continue;
        dfs(y);
    }
}
void tarjan(int x,int in_edge){
    dfn[x]=low[x]=++num;
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i];
        if(!dfn[y]){
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x])    bridge[i]=bridge[i^1]=true;
        }
        else    if(i!=(in_edge^1))    low[x]=min(low[x],dfn[y]);
    }
}
int main(){
    cin>>n>>m;
    tot=1;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&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(!c[i]){
            ++dcc;
            dfs(i);
        }
    for(int i=2;i<=tot;i++){
        int x=ver[i^1],y=ver[i];
        if(c[x]==c[y])    continue;
        in[c[y]]++;
    }
    for(int i=1;i<=dcc;i++)
        if(in[i]==1)    ans++;
    printf("%lld",(ans+1)/2);
    return 0;
}