C++算法庫中的并查集實現(xiàn)

在C++中，可以通過以下方式實現(xiàn)并查集（Disjoint Set）：

#include <vector>

class DisjointSet {
public:
    DisjointSet(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int u) {
        if (parent[u] != u) {
            parent[u] = find(parent[u]);
        }
        return parent[u];
    }

    void merge(int u, int v) {
        int pu = find(u);
        int pv = find(v);
        if (pu != pv) {
            if (rank[pu] < rank[pv]) {
                parent[pu] = pv;
            } else if (rank[pu] > rank[pv]) {
                parent[pv] = pu;
            } else {
                parent[pu] = pv;
                rank[pv]++;
            }
        }
    }

private:
    std::vector<int> parent;
    std::vector<int> rank;
};

使用示例：

#include <iostream>

int main() {
    DisjointSet ds(5);

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

    std::cout << ds.find(2) << std::endl; // Output: 0
    std::cout << ds.find(4) << std::endl; // Output: 3

    return 0;
}

在上面的示例中，定義了一個DisjointSet類，包含了find和merge兩個方法，分別用于查找元素所在的集合和合并兩個集合?？梢愿鶕?jù)實際需求進行修改和擴展。