题解 | #【模板】并查集#

考虑到题目需要求出人数最多的班级，也就是秩最大的班级，引入ranks数组记录，同时小挂大似乎也是一种优化，最后的班级数量再来一遍遍历，如果父节点是自身，说明它就是该集合的父节点(已经使用了路径压缩)

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
vector<int>f,ranks;
void build(){
	for(int i=1;i<=n;i++){
		f[i]=i;
		ranks[i]=1;
	}
}
int find_f(int x){
	if(f[x]!=x){//如果父节点不是自己，往上一直搜直到搜到父节点等于自身的，也即集合的父节点，指向它即可，这就是路径压缩
		f[x]=find_f(f[x]);
	}
	return f[x];
}
void union_set(int x,int y){
	int f_x=find_f(x),f_y=find_f(y);
	if(f[x]!=f[y]){
		if(ranks[f_x]>ranks[f_y]){//小挂大
			f[f_y]=f_x;
			ranks[f_x]+=ranks[f_y];
			ans=max(ranks[f_x],ans);
		}
		else{
			f[f_x]=f_y;
			ranks[f_y]+=ranks[f_x];
			ans=max(ranks[f_y],ans);//每次比较人数
		}
	}
}
int main(){
	cin>>n>>m;
	int classes=0;
	f.resize(n+1);
	ranks.resize(n+1);
	build();
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		union_set(u,v);//由于同一行的是同班的，直接联合
	}
	for(int i=1;i<=n;i++){//来个遍历统计班级数量
		if(f[i]==i){
			classes++;
		}
	}
	cout<<classes<<' '<<ans<<endl;
}