首页 > 代码库 > 【HDU1856】More is better（并查集基础题）

【HDU1856】More is better（并查集基础题）

2024-07-13 11:58:15   219人阅读

裸并查集，但有二坑：

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

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

 

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <numeric> 7 #include <string> 8 #include <cctype> 9 #include <cmath>10 11 #pragma comment(linker, "/STACK:102400000,102400000")12 using namespace std;13 14 const int maxn = 1e7 + 10;15 int father[maxn], ans[maxn], res;16 17 int getFather (int x) {18     if (x != father[x]) {19         father[x] = getFather (father[x]);20     }21     return father[x];22 }23 24 void Union (int p, int q) {25     int x = getFather (p);26     int y = getFather (q);27     if (x != y) {28         father[y] = x;29         ans[x] += ans[y];30         res = max (ans[x], res);31     }32 }33 34 int main () {35     int n;36     while (~scanf("%d", &n)) {37         for (int i = 0 ; i < maxn; ++ i) {38             father[i] = i;39             ans[i] = 1;40         }41 42         int x, y, MAXX = 0;43         res = 1;44         for (int i = 0 ; i < n; ++ i) {45             scanf("%d%d", &x, &y);46             Union (x, y);47             MAXX = max(x, MAXX);48             MAXX = max(y, MAXX);49         }50 51         cout << res << endl;52     }53     return 0;54 }


联系
我们