POJ 3177 Redundant Paths（边双连通分量）

【题目链接】 http://poj.org/problem?id=3177

【题目大意】

　　给出一张图，问增加几条边，使得整张图构成双连通分量

【题解】

　　首先我们对图进行双连通分量缩点，
　　那么问题就转化为给出一棵树，加边使得其成为边双连通分量的最小边数，
　　只要从叶节点连一条边到任意节点，那么就可以使得这个叶节点加入到双连通分量中，
　　那么优先叶节点和叶节点连接，所以其答案为(叶节点+1)/2

【代码】

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <vector>

using namespace std;

const int N=5010,M=10010;

int e[M][2],cut[M],g[N],v[M<<1],nxt[M<<1],ed=1;

int f[N],dfn[N],low[N],num,cnt,from[N],d[N];

void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}

void tarjan(int x){

    dfn[x]=low[x]=++num;

    for(int i=g[x];i;i=nxt[i])if(!dfn[v[i]]){

        f[v[i]]=i>>1,tarjan(v[i]);

        if(low[x]>low[v[i]])low[x]=low[v[i]];

    }else if(f[x]!=(i>>1)&&low[x]>dfn[v[i]])low[x]=dfn[v[i]];

    if(f[x]&&low[x]==dfn[x])cut[f[x]]=1;

}

void dfs(int x,int y){

    from[x]=y;

    for(int i=g[x];i;i=nxt[i])if(!from[v[i]]&&!cut[i>>1])dfs(v[i],y);

}

int n,m;

int main(){

    while(~scanf("%d%d",&n,&m)){

        memset(g,0,sizeof(g));

        memset(d,0,sizeof(d));

        memset(from,0,sizeof(from));

        memset(f,0,sizeof(f));

        memset(cut,0,sizeof(cut));

        num=0; ed=1; // 求边双连通分量时，ed一定要为1

        for(int i=1;i<=m;i++){

            int u,v;

            scanf("%d%d",&u,&v);

            e[i][0]=u; e[i][1]=v;

            add(u,v);add(v,u);

        }tarjan(1); cnt=0;

        for(int i=1;i<=n;i++)if(!from[i])dfs(i,++cnt);

        for(int i=1;i<=m;i++){

            if(from[e[i][0]]!=from[e[i][1]]){

                d[from[e[i][0]]]++;

                d[from[e[i][1]]]++;

            }

        }int res=0;

		    //for(int i=1;i<=n;i++)printf("%d %d\n",from[i],d[i]);

        for(int i=1;i<=n;i++)if(d[i]==1)res++;

        printf("%d\n",(res+1)/2);

    }return 0;

}