用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) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

int main() {
    UnionFind uf(5); // 创建一个大小为5的并查集
    uf.merge(0, 1); // 合并0和1所在的集合
    uf.merge(2, 3); // 合并2和3所在的集合
    uf.merge(3, 4); // 合并3和4所在的集合

    cout << uf.find(0) << endl; // 0所在的集合的代表元素是0
    cout << uf.find(1) << endl; // 1所在的集合的代表元素是0
    cout << uf.find(2) << endl; // 2所在的集合的代表元素是2
    cout << uf.find(3) << endl; // 3所在的集合的代表元素是2
    cout << uf.find(4) << endl; // 4所在的集合的代表元素是2

    return 0;
}

在这个示例代码中，我们定义了一个UnionFind类，它包含两个私有成员变量parent和rank，以及两个公有成员函数find和merge。

parent是一个整数类型的向量，用于存储每个节点的父亲节点。在初始化时，我们将每个节点的父亲节点都设置为自己。

rank也是一个整数类型的向量，用于存储每个节点的秩（树的高度）。在初始化时，我们将每个节点的秩都设置为0。

find函数用于查找元素所在的集合，并进行路径压缩。具体地，它递归地查找元素所在的集合的代表元素，将路径上的所有节点的父亲节点都设置为代表元素，以实现路径压缩。

merge函数用于合并两个元素所在的集合。具体地，它先分别找到两个元素所在的集合的代表元素，然后比较它们的秩，将秩较小的集合合并到秩较大的集合中。如果两个集合的秩相同，则将其中一个集合的根节点作为另一个集合的子节点，并将该集合的秩加1。

在main函数中，我们创建了一个大小为5的并查集，然后调用merge函数合并0和1所在的集合，2和3所在的集合，3和4所在的集合。最后，我们调用find函数查找0、1、2、3、4所在的集合的代表元素，并输出结果。