题意：房间里一共有 \(10^7\)个人，人与人直接有直接或者间接的朋友关系。
最多可以选择多少有朋友关系的人?
分析：求最大连通块。
- 带权并查集，父节点同时维护数量。
- dfs/bfs 求最大连通块。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e7 + 10, INF = 0x3f3f3f3f;
int n, m, f[N], cnt[N];
int find(int u) {
return u == f[u] ? u : f[u] = find(f[u]);
}
int main() {
while (~scanf("%d", &n)) {
for (int i = 0; i <= 1e7; i++)
f[i] = i, cnt[i] = 1;
for (int i = 1, u, v; i <= n; i++) {
scanf("%d%d", &u, &v);
int fu = find(u), fv = find(v);
if (fu != fv) {
f[fu] = fv, cnt[fv] += cnt[fu];
}
}
int ans = 0;
for (int i = 0; i <= 1e7; i++)
ans = max(ans, cnt[i]);
printf("%d\n", ans);
}
return 0;
}