c++中如何实现并查集的合并_c++并查集合并方法

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

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;

public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;  // 初始化：每个节点指向自己
        }
    }

    // 查找根节点（带路径压缩）
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩：直接连到根
        }
        return parent[x];
    }

    // 合并两个集合（按秩合并）
    void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) return;  // 已在同一集合

        // 按秩合并：将低秩树接到高秩树下
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;  // 秩相同，合并后根的秩加1
        }
    }

    // 判断是否在同一集合
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    UnionFind uf(5);  // 创建5个元素的并查集

    uf.merge(0, 1);
    uf.merge(1, 2);
    uf.merge(3, 4);

    cout << uf.connected(0, 2) << endl;  // 输出 1（true）
    cout << uf.connected(0, 3) << endl;  // 输出 0（false）

    uf.merge(2, 3);
    cout << uf.connected(0, 4) << endl;  // 输出 1（true）

    return 0;
}