题目链接
题意：
有10000000个元素，给定n对数字A,B，将A,B所在的集合合并（一开始每个元素所在的集合只有它自己），选择一个元素所在的集合，求这个集合的元素个数最多为多少？
思路：
典型的并查集题型，但除了要用到基础的合并外，还多了求集合大小和最大的集合大小的操作，这是需要自己去思考并解决的，首先如果把一千万个元素都扫一遍，显然会超时。那么既然大多数的元素都没有被合并，那么只需要管出现了的元素就行了，我用了set来记录出现过的元素。而至于元素的大小，只需要在扫的时候将同一集合的个数++就行了。一趟下来的时间复杂度为O(nlog2(n))。
100分AC代码：
#include <bits/stdc++.h>
using namespace std;
int m,n=100000;
int f[100005];
int find(int x){
if(f[x]==x)return x;
return f[x]=find(f[x]);
}
void uni(int x,int y){
int fx=find(x);
int fy=find(y);
f[fx]=fy;
}
int main() {
while(cin>>m){
int ans=1;//注意ans要为1
map<int,int> a;
set<int> b;
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
uni(x,y);
b.insert(x);
b.insert(y);
}
for(set<int>::iterator it=b.begin();it!=b.end();it++){
a[find(*it)]++;
ans=max(ans,a[find(*it)]);
}
cout<<ans<<endl;
}
return 0;
}
大功告成！