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

• 使用并查集，来记录所有人的关系
• 再将每个人的顶送入set中，set的长度就是班级数量
• 再用一个循环找到最大班级即可

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;

int st[N], f[N], s[N], n, m;
set<int> ss;
void init(int n) {
	for (int i = 1; i < n; i++) {	// 初始化 
		f[i] = i;
		s[i] = 1;
	}
}

int find(int i) {
	int size = 0;	// 沿途收集了几个点
	while (i != f[i]) {	// 还没有到顶
		st[size++] = i;	// 收集沿途上的所有点
		i = f[i];	// 向上查询是否到顶
	}
	while (size > 0) {
		f[st[--size]] = i;	// 扁平化 
	}
	return i;	// 返回父节点 
}

bool isSameSet(int x, int y) {
	return find(x) == find(y);
}

void merge(int x, int y) {
	int fx = find(x);
	int fy = find(y);
	if (fx == fy) return ;	// 顶相同说明是同一个集合，可以不用合并了
	if (s[fx] > s[fy]) {	// fx > fy 小挂大
		s[fx] += s[fy];
		f[fy] = fx;
	} else {
		s[fy] += s[fx];
		f[fx] = fy;
	}
}


int main() {
	cin >> n >> m;
	init(n + 1);	// 初始化
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		merge(x, y);	// 合并两个集合		
	}
	for (int i = 1; i <= n; i++) {
		ss.insert(find(i));	// 使用set得到有多少个不同的顶的数量
	}
	int val = 0;
	for (auto it : ss) {
		val = max(val, s[it]);
	}
	cout << ss.size() << ' ' << val << '\n';
	return 0;
}