并查集之求集合的元素的最大个数----hdu1856 more is better

 1 #include<cstdio>
 2 #define N 10000005
 3 int pre[N];
 4 int num[N];
 5 void init()
 6 {
 7     for(int i=1; i<=N; i++)
 8     {
 9         num[i]=1;
10         pre[i]=i;
11     }
12 }
13 int find(int x)
14 {
15     int r=x;
16     while(r!=pre[r])
17         r=pre[r];
18     int i=x,j;
19     while(i!=r)
20     {
21         j=pre[i];
22         pre[i]=r;
23         i=j;
24     }
25     return r;
26 }
27 void merge(int x,int y)
28 {
29     int fx=find(x);
30     int fy=find(y);
31     if(fx!=fy)
32     {
33         num[fy]+=num[fx];
34         pre[fx]=fy;
35     }
36 }
37 int main()
38 {
39     int n;
40     while(~scanf("%d",&n))
41     {
42         if(n==0)
43         {
44             printf("1
");
45             continue;
46         }
47         init();
48         int max=0;
49         while(n--)
50         {
51             int x,y;
52             scanf("%d%d",&x,&y);
53             if(x>max)  max=x;
54             if(y>max)  max=y;
55             merge(x,y);
56         }
57         int maxn=0;
58         for(int i=1; i<=max; i++)
59             if(num[i]>maxn)
60                 maxn=num[i];
61         printf("%d
",maxn);
62     }
63     return 0;
64 }

上面是AC代码，核心思想就是求出集合元素个数的最大值，然而我们知道，寻找每一位元素的时候通过merge[]集合寻找到根节点是否相同，如果不相同，则将pre【】集合的根节点更新，如此我们可以在更新的时候进行计数，num[]就是一个计数集合，我们只需要寻找最大值就可以了。。。欢迎提问，别忘了关注呦！！！