hdu4496并查集的删边操作

题意:

给你一个图,问你删除一些边后还有几个连通快..

思路:

典型的并查集删边操作,并查集的删边就是先把不删除的边并查集一边(本题没有不删除的边),然后逆序吧所有要删除的边以点点加到并查集数组里,如果当前的边的两个点不是一个集合的,那么删除当前边后就会使连通快加一...

#include<stdio.h>

#include<string.h>

#define N 11000



typedef struct

{

   int a ,b ,c;

}EDGE;

int mer[N];

EDGE E[N*10];

int finds(int x)

{

   return x == mer[x] ? x : mer[x] = finds(mer[x]);

}

int main ()

{

   int n ,m ,a ,b ,i;

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

   {

      for(i = 1 ;i <= n ;i ++)

      mer[i] = i;

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

      {

         scanf("%d %d" ,&a ,&b);

         E[i].a = a + 1;

         E[i].b = b + 1;

      }

      int sum = n;

      for(i = m;i >= 1;i --)

      {

         a = finds(E[i].a);

         b = finds(E[i].b);

         E[i].c = sum;

         if(a != b) sum --;

         mer[a] = b;

      }

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

      printf("%d\n" ,E[i].c);

   }

   return 0;

}

巴特西

hdu4496并查集的删边操作

最新文章

热门文章