C++如何实现并查集 C++并查集的数据结构与实现

#include <iostream>
#include <vector>

using namespace std;

class DisjointSet {
public:
    DisjointSet(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i; // 初始化每个元素的父节点指向自己
        }
    }

    // 查找元素x所属集合的代表（带路径压缩）
    int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]); // 路径压缩：将x的父节点直接指向根节点
        }
        return parent[x];
    }

    // 合并包含元素x和元素y的集合（按秩合并）
    void Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);

        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++; // 如果秩相同，则将其中一个树的秩增加1
            }
        }
    }

private:
    vector<int> parent; // 存储每个元素的父节点
    vector<int> rank;   // 存储每个集合的秩（树的高度的一个上界）
};

int main() {
    DisjointSet ds(10); // 创建一个包含10个元素的并查集

    ds.Union(0, 1);
    ds.Union(2, 3);
    ds.Union(4, 5);
    ds.Union(0, 2); // 将包含0和2的集合合并

    cout << "Find(0) = " << ds.Find(0) << endl; // 应该和Find(2)相同
    cout << "Find(2) = " << ds.Find(2) << endl;
    cout << "Find(1) = " << ds.Find(1) << endl; // 应该和Find(0), Find(2)相同
    cout << "Find(4) = " << ds.Find(4) << endl;
    cout << "Find(5) = " << ds.Find(5) << endl;

    return 0;
}