2649: More is better 并查集

王先生想要一些男孩帮助他完成一个项目。因为项目比较复杂，男生来的越多越好。当然有一定的要求。

王先生选择了一个足够容纳孩子们的房间。没有被选中的男孩必须立即离开房间。一开始房间里有10000000个男孩，编号从1到10000000。经过王先生的选择，他们中仍然在这个房间里的任何两个应该是朋友（直接或间接），或者只剩下一个男孩。给定所有直接朋友对，你应该决定最好的方法。

输入

输入的第一行包含一个整数 n (0 ≤ n ≤ 100 000) - 直接朋友对的数量。接下来的 n 行每行包含一对由一个空格分隔的数字 A 和 B，这表明 A 和 B 是直接朋友。(A ≠ B, 1 ≤ A, B ≤ 10000000)

输出

一行输出正好包含一个整数，等于王先生最多可以保留的男孩数。

样例输入

4
1 2
3 4
5 6
1 6
4
1 2
3 4
5 6
7 8

样例输出

4
2

提示

A和B是朋友（直接或间接），B和C是朋友（直接或间接），
那么A和C也是朋友（间接）。

在第一个示例中，{1,2,5,6} 是结果。
在第二个样本中，{1,2}、{3,4}、{5,6}、{7,8} 是四种答案。

题意：并查集后询问最大家族人数数量

#include<bits/stdc++.h>
using namespace std; 
const int N = 1e7+10,inf = 0x3f3f3f3f,M = 2*1e4+10;
int f[N],a[N],maxn,x[M],y[M];
int n,ans;
int find(int x) //找到x的祖先 x=2  f[x] = 3
{
    if(f[x]!=x)f[x] = find(f[x]); //如果x的爹不是自己，那么去寻找爹中爹
    return f[x];
} 
void merger(int x,int y) //合并x和y两个集合
{
    int fx = find(x);
    int fy = find(y);
    if(a[fx]<a[fy])swap(fx,fy); //交换位置，保证fx所在的关系网人数是比较多的 
    a[fx] = a[fx] + a[fy];
    ans = max(ans,a[fx]);
    f[fy] = fx; //fy的祖先是fx 
}
int main()
{
    while(cin>>n)
    {
        ans = 0;
        for(int i=1;i<=N;i++)f[i] = i,a[i] = 1;
        for(int i=1;i<=n;i++)
        {
            int x,y; cin>>x>>y;
            if(find(x)!=find(y))merger(x,y);
        }
        cout<<ans<<endl;
    }
    return 0;
}