题解 | #并查集的实现#路径压缩 + 小挂大

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000001;

int father[MAXN];  // 每个节点的父节点
int group_size[MAXN];    // 每个集合的大小
int st[MAXN];   // 用于路径压缩的栈
int n;  // 节点数量

// 初始化并查集
void build() {
    for (int i = 0; i <= n; i++) {
        father[i] = i;   // 自己是自己的父节点
        group_size[i] = 1;      // 初始大小为1
    }
}

// 查找并返回i的根节点，带路径压缩
int find(int i) {
    // 沿途收集路径上的所有节点
    int size = 0;
    while (i != father[i]) {
        st[size++] = i;  // 将当前节点压入栈
        i = father[i];      // 一直往上找
    }
    // 路径压缩，所有节点都直接指向根节点
    while (size > 0) {
        father[st[--size]] = i;
    }
    return i;  // 返回根节点
}

// 判断x和y是否在同一集合中
bool isSameSet(int x, int y) {
    return find(x) == find(y);  // 如果根节点相同，则在同一个集合
}

// 合并x和y所在的两个集合
void unionSets(int x, int y) {
    int fx = find(x);  // 找到x的根节点
    int fy = find(y);  // 找到y的根节点
    if (fx != fy) {  // 如果x和y不在同一个集合
        // fx是集合的代表：拿大小
        // fy是集合的代表：拿大小
        if (group_size[fx] >= group_size[fy]) {
            group_size[fx] += group_size[fy];  // 合并两个集合
            father[fy] = fx;       // 将fy的根节点指向fx
        } else {
            group_size[fy] += group_size[fx];
            father[fx] = fy;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);  // 提高输入输出效率
    cin.tie(nullptr);  // 解除cin与cout的绑定
    cout.tie(nullptr);

    // 输入处理
    int m;
    while (cin >> n) {  // 读取节点数
        build();  // 初始化并查集
        cin >> m;  // 读取操作次数
        for (int i = 0; i < m; i++) {
            int op, x, y;
            cin >> op >> x >> y;
            if (op == 1) {  // 查询是否在同一集合
                cout << (isSameSet(x, y) ? "Yes" : "No") << endl;
            } else {  // 合并集合
                unionSets(x, y);
            }
        }
    }

    return 0;
}