题解 | 【模板】并查集

#include <iostream>
#include <vector>
using namespace std;

//手写一个并查集
class UnionFind{
    private:
    vector<int> parent;//parent[i]记录节点i的父节点
    vector<int> size;  //size[i]记录以结点i为根的数的大小

    public:
    UnionFind(int n){//构造函数，确定parent和size数组的大小，确定并查集的容量
        parent.resize(n);
        size.resize(n, 1);//初始时每个元素自己组成一个集合，所在集合大小均为1
        //parent中每个结点的父节点均为自己
        for(int i = 0; i < n; i++){
            parent[i] = i;
        }
    }

    //查找函数，查找结点i所在树的根节点
    int Find(int i){
        if(parent[i] != i){
            parent[i] = Find(parent[i]);//递归查找,路径压缩
        }
        return parent[i];
    }

    //合并函数，合并两个集合
    void Uni(int i, int j){
        int rooti = Find(i);
        int rootj = Find(j);
        if(rooti == rootj){
            return;
        }
        else if(size[rooti] > size[rootj]){//按照大小合并，大小小的合并到大小大的集合中
            parent[rootj] = rooti;
            size[rooti] += size[rootj];
            return;
        }
        else{
            parent[rooti] = rootj;
            size[rootj] += size[rooti];
            return;
        }
    }

    //查询大小函数，返回元素i所在集合的大小
    int Size(int i){
        int x = Find(i);
        return size[x];
    }
 
};

int main() {
    //输入数据
    int n, q;
    cin >> n >> q;
    
    //初始化并查集
    UnionFind uf(n + 1);

    //处理q行指令
    for(int i = 0; i < q; i++){
        int op;
        cin >> op;
        if(op == 1){
            int i, j;
            cin >> i >> j;
            uf.Uni(i, j);
        }
        else if(op == 2){
            int i, j;
            cin >> i >> j;
            if(uf.Find(i) == uf.Find(j)){
                cout << "YES" << '\n';
            }
            else{
                cout << "NO" << '\n';
            }
        }
        else{
            int i;
            cin >> i;
            cout << uf.Size(i) << '\n';
        }
    }

    return 0;
}
// 64 位输出请用 printf("%lld")