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         else
25         {
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
",cnt);
51     }
52 }