HDU 1213 How Many Tables (并查集)

一时失言乱红尘 2022-06-05 01:55 280阅读 0赞 
  1. //题意自己看，不会度娘
  3. #include <stdio.h>
  4. #include <string.h>
  5. int a[1050];
  6. int merge(int x)
  7. {
  8.     int r=x;
  9.     while(a[r]!=r) 
  10.     r=a[r];
  11.     return r;
  12. }
  13. void findx(int x,int y)
  14. {
  15.     int fx=merge(x);
  16.     int fy=merge(y);
  17.     if(fx!=fy)
  18.     a[fx]=fy;
  19. } 
  20. int main(int argc, char *argv[])
  21. {
  22.     int t;
  23.     int n,m,i;
  24.     int x,y;
  25.     int flag;
  26.     scanf("%d",&t);
  27.     while(t--)
  28.     {
  29.         scanf("%d",&n);
  30.         for(i=1;i<=n;i++)
  31.             a[i]=i;
  32.         for(scanf("%d",&m);m>0;m--)
  33.         {
  34.             scanf("%d %d",&x,&y);
  35.             findx(x,y);
  36.         }
  37.         for(flag=0,i=1;i<=n;i++)
  38.         if(a[i]==i)
  39.         flag++;
  40.         printf("%d\n",flag);    
  41.     }        
  42.     return 0;
  43. }
  45. //Start-ZJ
  47. //2017/11/14/19:42

发表评论

表情：
评论列表 （有 0 条评论，280人围观）

还没有评论，来说两句吧...

相关阅读