Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 327680/102400 K (Java/Others)
Total Submission(s): 14530 Accepted Submission(s): 5334
#include <iostream> #include <stack> #include <cstring> #include <cstdio> #include <string> #include <algorithm> #include <queue> #include <set> #include <map> using namespace std; /* 并查集,并记录每个集合的个数,取最大; 但是a, b范围很大,采用map; 为了方便,记录集合个数也用map; map超时,百度了下,居然可以开10000005这么大的数组 */ #define ms(arr, val) memset(arr, val, sizeof(arr)) #define N 10000005 #define INF 0x3fffffff #define vint vector<int> #define sint set<int> #define mint map<int, int> int mp[N], con[N]; int ans; int find(int x)//查找 { int fx = x; while (mp[fx]) { fx = mp[fx]; } int t = x; while (t != fx)/*路径压缩*/ { x = mp[t]; mp[t] = fx; t = x; } return fx; } bool _union(int fx, int fy)//合并 { if (fx == fy) { return false; } mp[fy] = fx;/*将fy并到fx上*/ con[fx] += con[fy]; if (con[fx] > ans) { ans = con[fx]; } return true; } int main() { int n, a, b; while (cin >> n) { ms(mp, 0); ms(con, 0); ans = 0; while (n--) { cin >> a >> b; if (!con[a]) { con[a] = 1; } if (!con[b]) { con[b] = 1; } _union(find(a), find(b)); } if (!ans)//没有则为1 { ans = 1; } cout << ans << endl; } return 0; }
hdu 1856 More is better,布布扣,bubuko.com
原文:http://www.cnblogs.com/jecyhw/p/3897566.html