并查集hdu畅通工程

View Code
 1 #include "stdio.h"
 2 int bin[1002];
 3 
 4 int findx(int x)
 5 {
 6     int r,j,i;
 7     r = x;
 8     while (bin[r] != r)
 9         r = bin[r];
10     i = x;
11     while (i != r)
12     {
13         j = bin[i];
14         bin[i] = r;
15         i = j;
16     }
17     return r;
18 }
19 
20 void merge(int x,int y)
21 {
22     int fx,fy;
23     fx = findx(x);
24     fy = findx(y);
25     if(fx != fy)
26         bin[fx] = fy;
27 }
28 
29 int main()
30 {
31     int n,m,i,x,y,count;
32     while(scanf("%d",&n),n)
33     {
34         for(i=1; i<=n; i++)
35             bin[i] = i;
36         for(scanf("%d",&m); m>0; m--)
37         {
38             scanf("%d %d",&x,&y);
39             merge(x,y);
40         }
41         for(count=-1, i=1; i<=n; i++)
42             if(bin[i] == i)
43                 count ++;
44         printf("%d\n",count);
45     }
46 }