题目链接

题意：

​ 有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;
}

大功告成！