因为人的编号比较大，但是输入的数据最多是10w行，所以可得出最多也就20w人，所以可以进行一下离散化处理，这样数据就会毫无压力
#include<iostream> #include<algorithm> #include<stdio.h> #include<math.h> #include< string.h> #include<queue> #include<stack> using namespace std; const int maxn = 300005; int f[maxn], p[maxn]; // p数组保存离散化后的数据 int sum[maxn]; // 保存以这点为根的数有多少个 struct node{ int u, v;}e[maxn]; // 保存边 int Find( int x) { if(f[x] != x) f[x] = Find(f[x]); return f[x]; } int main() { int M; while(scanf( " %d ", &M) != EOF) { int i, k= 0, N; for(i= 0; i<M; i++) { scanf( " %d%d ", &e[i].u, &e[i].v); p[k++] = e[i].u, p[k++] = e[i].v; } sort(p, p+k); // 去重复函数，返回去除重复后最后一个数的地址，减p可以算出有多少个不重复元素 N = unique(p, p+k) - p; for(i= 0; i<N; i++) f[i] = i, sum[i] = 0; for(i= 0; i<M; i++) { int u = lower_bound(p, p+N, e[i].u)-p; // 二分查找函数 int v = lower_bound(p, p+N, e[i].v)-p; u = Find(u), v = Find(v); if(u != v) f[v] = u; } int ans = 1; for(i= 0; i<N; i++) { k = Find(i); sum[k]++; ans = max(sum[k], ans); } printf( " %d\n ", ans); } return 0;
}