【HDU1856】More is better(并查集基础题)

裸并查集,但有二坑:

1.需要路径压缩,不写的话会TLE

2.根据题目大意,如果0组男孩合作的话,应该最大的子集元素数目为1.所以res初始化为1即可。

 #include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <string>
#include <cctype>
#include <cmath> #pragma comment(linker, "/STACK:102400000,102400000")
using namespace std; const int maxn = 1e7 + ;
int father[maxn], ans[maxn], res; int getFather (int x) {
if (x != father[x]) {
father[x] = getFather (father[x]);
}
return father[x];
} void Union (int p, int q) {
int x = getFather (p);
int y = getFather (q);
if (x != y) {
father[y] = x;
ans[x] += ans[y];
res = max (ans[x], res);
}
} int main () {
int n;
while (~scanf("%d", &n)) {
for (int i = ; i < maxn; ++ i) {
father[i] = i;
ans[i] = ;
} int x, y, MAXX = ;
res = ;
for (int i = ; i < n; ++ i) {
scanf("%d%d", &x, &y);
Union (x, y);
MAXX = max(x, MAXX);
MAXX = max(y, MAXX);
} cout << res << endl;
}
return ;
}
上一篇:MVC下设置默认页为index.html


下一篇:[转帖]Oracle 补丁体系(PSR/PSU/CPU) 及 opatch 工具 介绍