并查集

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

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;
}