Poj3177 tarjan算法求双连通分量

题目大意：给定一个无向连通图，问天几条边可以使它变成一个双连通图。

算法思路：tarjan算法模板。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
#define MAXN 10005
int n,m;
typedef struct Edge
{
    int u;
    int v;
    int c;
};
Edge edges[MAXN*20];
int head[MAXN],next[MAXN],a,b,e,times,cnt;
int dfn[MAXN],low[MAXN],group[MAXN],degree[MAXN];
bool visited[MAXN];
stack<int>stk;
void addNode(int u,int v)
{
    edges[e].u=u;
    edges[e].v=v;
    next[e]=head[u];
    head[u]=e++;
}

void tarjan(int u,int fa)
{

    dfn[u]=low[u]=times++;
    stk.push(u);
    bool flag=true;
    for(int i=head[u];i+1;i=next[i])
    {
        if(flag&&edges[i].v==fa)
        {
            flag=false;
            continue;
        }

        if(!dfn[edges[i].v])
        {
            tarjan(edges[i].v,u);
            low[u]=min(low[u],low[edges[i].v]);
        }
        else
        {
            low[u]=min(low[u],dfn[edges[i].v]);
        }
    }
    if(low[u]==dfn[u])
    {
        int v;
        do
        {
            v=stk.top();
            stk.pop();
            group[v]=cnt;
        }while(v!=u);
        cnt++;
    }


}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        e=0;
        cnt=1;
        times=0;
        memset(head,-1,sizeof(head));
        memset(next,-1,sizeof(next));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(visited,false,sizeof(visited));
        memset(degree,0,sizeof(degree));
        memset(group,0,sizeof(group));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            addNode(a,b);
            addNode(b,a);
        }

        bool isem=true;
        tarjan(1,-1);

       for(int i=1;i<=n;i++)
       {
            for(int j=head[i];j+1;j=next[j])
            {
                if(group[i]!=group[edges[j].v])
                {
                    degree[group[i]]++;
                    degree[group[edges[j].v]]++;
                }
            }
       }
       int ans=0;
        for(int i=1;i<cnt;i++)
        {
            if(degree[i]==2)
            {
                ans++;
            }
        }
        printf("%d\n",(ans+1)/2);

    }

    return 0;

}