hdu-1856 More is better---带权并查集

题目链接：

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

题目大意：

一个并查集计算每个集合的元素找出元素最多的那个集合，输出元素的个数

解题思路：

输入n=0时也应该输出1

可以用set储存每个元素，Map更新每个元素的根节点的权值

还可以用带权并查集，在合并集合的时候，合并带权的数组（该数组表示集合中的元素）

set&map版：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int T, n, m;
 4 const int maxn = 10000000 + 10;
 5 int cases;
 6 int p[maxn];
 7 void init()
 8 {
 9     for(int i = 0; i < maxn; i++)p[i] = i;
10 }
11 int Find(int x)
12 {
13     return x == p[x] ? x : p[x] = Find(p[x]);
14 }
15 set<int>s;
16 map<int, int>Map;
17 int main()
18 {
19     int n, x, y;
20     while(scanf("%d", &n) != EOF)
21     {
22         s.clear();
23         Map.clear();
24         init();
25         while(n--)
26         {
27             scanf("%d%d", &x, &y);
28             {
29                 p[Find(x)] = Find(y);
30                 s.insert(x);
31                 s.insert(y);
32             }
33         }
34         int ans = 1, t;
35         for(set<int>::iterator it = s.begin(); it != s.end(); it++)
36         {
37             t = Find(*it);
38             ans = max(ans, ++Map[t]);
39         }
40         printf("%d
", ans);
41     }
42     return 0;
43 }

带权并查集版：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int T, n, m;
 4 const int maxn = 10000000 + 10;
 5 int cases;
 6 int p[maxn], cnt[maxn];//cnt数组计数
 7 void init()
 8 {
 9     for(int i = 0; i < maxn; i++)p[i] = i, cnt[i] = 1;
10 }
11 int Find(int x)
12 {
13     return x == p[x] ? x : p[x] = Find(p[x]);
14 }
15 int main()
16 {
17     int n, x, y;
18     while(scanf("%d", &n) != EOF)
19     {
20         init();
21         while(n--)
22         {
23             scanf("%d%d", &x, &y);
24             {
25                 x = Find(x);
26                 y = Find(y);
27                 if(x != y)p[x]= y, cnt[y] += cnt[x];//x那颗树作为y的那棵树的子树
28 
29             }
30         }
31         int ans = cnt[0];
32         for(int i = 1; i < maxn; i++)
33             ans = max(ans, cnt[i]);
34         printf("%d
", ans);
35     }
36     return 0;
37 }