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

边双连通问题，与点双连通还是有区别的！！！

题意是给你一个图（本来是连通的），问你需要加多少边，使任意两点间，都有两条边不重复的路径；

先将所有的边双连通分量看做一个点，此时的图就变成了一棵树，则题目变成了在树种添一些边，使任意两点间有两条不重复的路径，答案为（叶子节点数+1）/ 2 ；

#include "stdio.h"   //poj 3177 边双连通问题

#include "string.h"

#define N 5050

#define M 10100

struct node

{

    int x,y;

    bool visit;

    int next;

}edge[2*M];

int idx,head[N];

void Init()

{

    idx = 0;

    memset(head,-1,sizeof(head));

}

void Add(int x,int y)

{

    edge[idx].x = x;

    edge[idx].y = y;

    edge[idx].visit = false;

    edge[idx].next = head[x];

    head[x] = idx++;

}

int time;

int low[N],dfn[N];

inline int MIN(int a,int b){ return a<b?a:b; }

int st[M],num;  //记录哪些点为桥

int stackk[2*M],top;  //模拟栈(本题栈中存的是点，不是边)

int countt; //记录有多少个双连通分量

int n,m;

bool mark[N];

int belong[N];

int du[N];

void lian_tong(int x)

{

    int t;

    while(1)

    {

        t = stackk[top];

        top--;

        belong[t] = countt;

        if(t==x) break;

    }

    countt++;

}

void DFS(int x)

{

    int i,y;

    stackk[++top] = x;

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

    for(i=head[x]; i!=-1; i=edge[i].next)

    {

        y = edge[i].y;

        if(edge[i].visit) continue;

        edge[i].visit = edge[i^1].visit = true;

        if(!dfn[y])

        {

            DFS(y);

            low[x] = MIN(low[x],low[y]);

            if(low[y]>dfn[x])

                st[num++] = i;  //记录桥（两边双连通分量必定由桥相连）

        }

        else

            low[x] = MIN(low[x],dfn[y]);

    }

    if(dfn[x]==low[x])

        lian_tong(x); //标记当前边双连通分量

}

int main()

{

    int i;

    int x,y;

    while(scanf("%d %d",&n,&m)!=EOF)

    {

        Init();

        for(i=0; i<m; ++i)

        {

            scanf("%d %d",&x,&y);

            Add(x,y);

            Add(y,x);

        }

        countt = 0;  //统计边双连通分量的个数

        num = 0;  //统计桥的条数

        top = 0; //栈

        time = 0;

        memset(dfn,0,sizeof(dfn));

        for(i=1; i<=n; ++i) belong[i] = i;

        DFS(1);

        memset(du,0,sizeof(du));

        for(i=0;i<num; ++i) //遍历每一个桥，统计每个边双连通分量的度

        {

            du[ belong[edge[st[i]].x] ] ++;

            du[ belong[edge[st[i]].y] ] ++;

        }

        int ans = 0;

        for(i=0; i<countt; ++i)

            if(du[i]==1) ans++;  //统计缩点后所形成的树种的叶子节点个数（度为1）

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

    }

    return 0;

}