（模板）并查集

题目描述：

体育课上，体育老师牛牛弄不清学生们都是哪个班级的，他只能随便找两个同学，问他们是不是一个班的，牛牛记下了属于同一个班的学生的序号，但是他弄不清自己教的班级的情况，请你帮助他。

假设体育老师的学生有n人，学号分别是1,2,...n，他的小本本记录了m行，每行记下了属于一个班级的两个同学的学号u, v.

请问他的学生一共属于几个班级？人数最多的班级有几个人？

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;
int fa[N],flag[N];
map<int,int> me;//map里前一个数存储根节点序号,后一个数存储当前人数

int find(int n)//查询根节点
{
    if(n!=fa[n])fa[n]=find(fa[n]);//路径压缩
    return fa[n];
}

bool cmp(pair<int,int>a,pair<int,int>b)//按人数降序排列
{
    return a.second>b.second;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int n,m,cla=0;
    cin>>n>>m;
    
    for(int i=1;i<=n;i++)fa[i]=i;
    
    while(m--)
    {
        int u,v;
        cin>>u>>v;
        if(find(u)!=find(v))fa[find(u)]=find(v);//这里建树时要格外注意，当两者已经有同一个根节点时不用将两点连接
    }
    for(int i=1;i<=n;i++)
    {
        if(!flag[find(i)])
        {
            me[find(i)]=1;
            flag[find(i)]=1;
            cla++;
        }
        else{
            me[find(i)]++;
        }
    }
    vector< pair<int,int> > ve(me.begin(),me.end());//map自定义排序需要借助pair
    sort(ve.begin(),ve.end(),cmp);
     
    cout<<cla<<' '<<ve[0].second;
    
    
}

后来发现可以用一个数组对每个集合的元素个数进行维护qwq,于是有了以下代码

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;
int fa[N],cnt[N];

int find(int n)
{
    if(n!=fa[n])fa[n]=find(fa[n]);
    return fa[n];
}


int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int n,m,cla;
    cin>>n>>m;cla=n;
    
    for(int i=1;i<=n;i++)fa[i]=i,cnt[i]=1;
    
    while(m--)
    {
        int u,v;
        cin>>u>>v;
        if(find(u)!=find(v))
        {
            cla--;
            cnt[find(v)]+=cnt[find(u)];
            fa[find(u)]=find(v);
        }
    }
    
    int ma=0;
    
    for(int i=1;i<=n;i++)
    {
        ma=max(ma,cnt[find(i)]);
    }
    
    cout<<cla<<' '<<ma;
     
}