首页 > 代码库 > hdu 1856 More is better

hdu 1856 More is better

http://acm.hdu.edu.cn/showproblem.php?pid=1856

这道题就是求一个集合里面最大的个数。 基本的并查集加一个步骤,将合并后的元素的个数保存在新的树根中。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 100010
 5 using namespace std;
 6 
 7 int f[maxn],a[maxn];
 8 int n,b,c;
 9 int max1=-1;
10 
11 int find1(int x)
12 {
13     if(x==f[x]) return x;
14     return f[x]=find1(f[x]);
15 }
16 
17 void union1(int aa,int b)
18 {
19     int fa=find1(aa);
20     int fb=find1(b);
21     if(fa!=fb)
22     {
23         f[fa]=fb;
24         a[fb]+=a[fa];
25         max1=max(max1,a[fb]);
26     }
27 }
28 
29 void inti()
30 {
31     for(int i=0; i<=maxn; i++)
32     {
33         f[i]=i;
34         a[i]=1;
35     }
36 }
37 
38 int main()
39 {
40     while(scanf("%d",&n)!=EOF)
41     {
42         inti();
43         max1=1;
44         for(int i=0; i<n; i++)
45         {
46             scanf("%d%d",&b,&c);
47             union1(b,c);
48         }
49         printf("%d\n",max1);
50     }
51     return 0;
52 }
View Code