http://acm.hdu.edu.cn/showproblem.php?pid=1856
Time Limit: 5000/1000 MS
(Java/Others) Memory Limit: 327680/102400 K
(Java/Others)
Total Submission(s): 12984 Accepted
Submission(s): 4756
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 10000000; int F[maxn], num[maxn]; int Find(int x) { if(F[x] == -1) return x; return Find(F[x]); } void Union(int x, int y) { int t1 = Find(x); int t2 = Find(y); if(t1 != t2) { if(num[t2] > num[t1]) { F[t1] = t2; num[t2] += num[t1]; } else { F[t2] = t1; num[t1] += num[t2]; } } } int main() { int n, a, b; while(~scanf("%d", &n)) { int maxx = 0; for(int i = 1; i <= maxn; i++) num[i] = 1; memset(F, -1, sizeof(F)); while(n--) { scanf("%d%d", &a, &b); if(maxx < a) maxx = a; if(maxx < b) maxx = b; Union(a, b); } int cnt = 1; for(int i = 1; i <= maxx; i++) if(cnt < num[i]) cnt = num[i]; printf("%d\n", cnt); } return 0; }
HDU 1856 More is better,并查集应用,布布扣,bubuko.com
原文:http://www.cnblogs.com/dzkang2011/p/morebetter.html