并查集

并查集 :并为合并(合并两个节点),查为查询(查询根节点),集是一个集合. 联通块问题 //各个节点的相连形成一个连通块.即使只有一个元素,因为可以自己连向自己所以也属于一个连通块 题解思路: 根据题意,我们可以使用并查集 先写一个 查 的函数,利用函数的递归不断寻找根(父)节点

int root(int x) {
	//寻找根节点
	return pre[x] = (pre[x] == x ? x : root(pre[x]));//路径压缩
}

接着可以写一个 并 的函数,利用 查函数 我们可以寻找到根节点,我们的合并只需要彼此的根节点相连即可

void merge(int x, int y) {
	pre[root(x)] = root(y);//合并
}

接下来就很简单了 AC代码:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
int pre[N], cnt[N];

int root(int x) {
	//寻找根节点
	return pre[x] = (pre[x] == x ? x : root(pre[x]));//路径压缩
}

void merge(int x, int y) {
	pre[root(x)] = root(y);//合并
}

bool iscon(int x, int y) {
	return root(x) == root(y);//判断是否连通
}

int main()
{
	std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++)pre[i] = i;//初始化

	//读入边
	for (int i = 1; i <= m; i++) {
		int u, v;cin>>u>>v;
		merge(u, v);
	}

	for(int i=1;i<=n;i++) cnt[root(i)]++;//统计连通分量

	vector<int>v;
	for (int i = 1; i <= n; i++)if (cnt[i])v.push_back(cnt[i]);

	sort(v.begin(), v.end());//排序

	for (auto& i : v) {
		cout << i << " ";
	}

	return 0;
}