POJ 3177 Redundant Paths 边双（重边）缩点

分析：边双缩点后，消环变树，然后答案就是所有叶子结点(即度为1的点)相连，为（sum+1）/2;

注：此题有坑，踩踩更健康，普通边双缩短默认没有无向图没有重边，但是这道题是有的

我们看，low数组是我们缩点的关键，记录最早的前驱，但是不能由父边过来，这是因为没有重边

当有重边时，父边也可以更新low数组，所以我们只需要忽略父边第一次出现，这样第二次出现时，就可以用了

这样就完美解决了重边问题

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <math.h>

#include <vector>

#include <stack>

using namespace std;

typedef long long LL;

const int N = 5e3+;

int head[N],tot,n,cnt,m;

struct Edge{

   int u,v,next;

}edge[N<<];

void add(int u,int v){

   edge[tot].u=u;

   edge[tot].v=v;

   edge[tot].next=head[u];

   head[u]=tot++;

}

int dfn[N],low[N],clk,bel[N],d[N];

stack<int>s;

void targin(int u,int f){

   dfn[u]=low[u]=++clk;

   s.push(u);

   bool flag=;//判断重边

   for(int i=head[u];~i;i=edge[i].next){

       int v=edge[i].v;

       if(v==f&&!flag){

        flag=;//记录重边出现次数，只跳过父边第一次出现

        continue;

       }

       if(!dfn[v]){

         targin(v,u);

         low[u]=min(low[u],low[v]);

       }

       else if(dfn[v]<low[u])low[u]=dfn[v];

   }

   if(dfn[u]==low[u]){

     ++cnt;

     int k;

     do{

        k=s.top();

        s.pop();

        bel[k]=cnt;

     }while(k!=u);

   }

}

int main(){

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

      scanf("%d%d",&n,&m);

      while(m--){

        int u,v;

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

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

      }

      targin(,-);

      for(int i=;i<tot;i+=){

         int k1=bel[edge[i].u],k2=bel[edge[i].v];

         if(k1==k2)continue;

         ++d[k1],++d[k2];

      }

      int sum=;

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

        printf("%d\n",++sum/);

      return ;

}