首页 > 代码库 > hdu 1232

hdu 1232

并查集 入门题

 1 #include<cstdio> 2 #include<memory.h> 3 int par[1000]; 4 int Find(int x) 5 { 6     while(par[x] > 0) 7         x = par[x]; 8     return x; 9 }10 void Merge(int x,int y)11 {12     int a,b;13     int tmp;14     a = Find(x);15     b = Find(y);16     if(a != b)17     {18         tmp = par[a] + par[b];19         if(par[a] < par[b]) //a 结点数多于 b的20         {21             par[b] = a;22             par[a] = tmp;23         }24         else25         {26             par[a] = b;27             par[b] = tmp;28         }29     }30 }31 int main()32 {33     freopen("input.txt","r",stdin);34     int x,y,n,m;35     int cnt;36     while(scanf("%d",&n) && n)37     {38         cnt = -1;39         scanf("%d",&m);40         memset(par,-1,sizeof(par));41         while(m--)42         {43             scanf("%d%d",&x,&y);44             Merge(x,y);45         }46         for(int i = 1; i <= n; i++)47         {48             if(par[i] <= -1) cnt++;49         }50         printf("%d\n",cnt);51     }52 }