hdu 1856 More is better，hdu1856
原題鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1856
簡單的並查集的運用，如下：
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<iostream>
4 #include<algorithm>
5 const int Max_N = 100050;
6 struct UnionFind{
7 int ans, par[Max_N], rank[Max_N], num[Max_N];
8 inline void init(int n){
9 ans = 1;
10 for (int i = 1; i < Max_N; i++){
11 par[i] = i;
12 rank[i] = 0;
13 num[i] = 1;
14 }
15 }
16 inline int find(int x){
17 while (x != par[x]){
18 x = par[x] = par[par[x]];
19 }
20 return x;
21 }
22 inline void unite(int x, int y){
23 x = find(x), y = find(y);
24 if (x == y) return;
25 if (rank[x] < rank[y]){
26 par[x] = y;
27 num[y] += num[x];
28 num[x] = 0;
29 ans = std::max(num[y], x);
30 } else {
31 par[y] = x;
32 num[x] += num[y];
33 num[y] = 0;
34 ans = std::max(num[x], ans);
35 if (rank[x] == rank[y]) rank[x]++;
36 }
37 }
38 }rec;
39 int main(){
40 #ifdef LOCAL
41 freopen("in.txt", "r", stdin);
42 freopen("out.txt", "w+", stdout);
43 #endif
44 int n, a, b;
45 while (~scanf("%d", &n)){
46 rec.init(n);
47 for (int i = 0; i < n; i++){
48 scanf("%d %d", &a, &b);
49 rec.unite(a, b);
50 }
51 printf("%d\n", rec.ans);
52 }
53 return 0;
54 }
View Code
