poj 3177&&poj 3352加边构双联通（有重边）用tarjan 模板求的

#include<stdio.h>/*
求边双联通分量和求强连通差不多，先缩点求出叶子节点的个数
*/
#include<string.h>
#define N  5100
struct node {
int u,v,next;
}bian[N*4];
int dfn[N],low[N],head[N],index,cnt,yong,stac[N],suo[N],vis[N],top,degree[N];
void init() {
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
index=0;cnt=0;yong=0;top=0;
memset(degree,0,sizeof(degree));
}
int Min(int a,int b) {
return a>b?b:a;
}
void addedge(int u,int v) {
bian[yong].u=u;
bian[yong].v=v;
bian[yong].next=head[u];
head[u]=yong++;
}
void tarjan(int u,int fa) {
  dfn[u]=low[u]=++index;
  vis[u]=1;
  stac[++top]=u;
  int i;
  for(i=head[u];i!=-1;i=bian[i].next) {
    int v=bian[i].v;
    if(i==(fa^1))continue;//注意优先级
    if(!dfn[v]) {
        tarjan(v,i);
        low[u]=Min(low[u],low[v]);
    }
    else if(vis[v])
        low[u]=Min(low[u],dfn[v]);
  }
  if(low[u]==dfn[u]) {
    cnt++;
    int t;
    do{
        t=stac[top--];
        vis[t]=0;
        suo[t]=cnt;
    }while(u!=t);
  }
}
int main() {
  int n,m,i,a,b;
  while(scanf("%d%d",&n,&m)!=EOF) {
    init();
    while(m--) {
        scanf("%d%d",&a,&b);
        addedge(a,b);
        addedge(b,a);
    }
for(i=1;i<=n;i++)
    if(!dfn[i])
        tarjan(i,-1);
        for(i=0;i<yong;i++) {
            int u,v;
            u=bian[i].u;
            v=bian[i].v;
            if(suo[u]!=suo[v])   {
                degree[suo[u]]++;
                degree[suo[v]]++;
            }
        }
        int leave=0;
        for(i=1;i<=cnt;i++)
            if(degree[i]==2)
            leave++;
        printf("%d
",(leave+1)/2);
  }
return 0;
}