以下是并查集（Union-Find）的C++实现代码，包含路径压缩和按秩合并两种优化方法：

一、基础实现（无优化）

#include <iostream>
#include <vector>

class UnionFind {
private:
    std::vector<int> parent;
    std::vector<int> rank; // 用于优化，记录树的高度

public:
    UnionFind(int size) {
        parent.resize(size);
        rank.resize(size, 0);
        for (int i = 0; i < size; ++i) {
            parent[i] = i; // 初始化每个元素的父节点为自身
        }
    }

    // 查找操作（带路径压缩）
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    // 合并操作（按秩合并）
    void unionSets(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]++; // 当两棵树高度相合并后根节点高度加1
            }
        }
    }

    // 判断是否连通
    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    int n = 10; // 假设有10个元素
    UnionFind uf(n);

    uf.unionSets(1, 2);
    uf.unionSets(2, 5);
    uf.unionSets(5, 6);
    uf.unionSets(6, 7);
    uf.unionSets(3, 8);
    uf.unionSets(8, 9);

    std::cout << "1 and 5 connected: " << (uf.isConnected(1, 5) ? "Yes" : "No") << std::endl;
    std::cout << "4 and 7 connected: " << (uf.isConnected(4, 7) ? "Yes" : "No") << std::endl;

    return 0;
}

二、代码说明

1. 初始化

   • parent数组用于存储每个元素的父节点，初始时每个元素的父节点是自身。

   • rank数组用于记录每个集合的树的高度（秩），初始值为0。

2. 查找操作（带路径压缩）

   • 通过递归查找根节点，并在查找过程中将路径上的所有节点直接指向根节点，减少后续查找的时间复杂度。

3. 合并操作（按秩合并）

   • 首先找到两个元素的根节点。

   • 将秩较小的树合并到秩较大的树中，如果两棵树高度相同，则任意选择一棵树作为合并后的根节点，并将其秩加1。

4. 判断连通性

   • 通过比较两个元素的根节点是否相同来判断是否连通。

三、优化说明

• 路径压缩 ：通过递归将路径上的节点直接指向根节点，使得后续查找操作的时间复杂度接近O（1）。

• 按秩合并 ：通过维护树的高度，避免树的高度过度增长，从而保持操作的平均时间复杂度为O（α（n）），其中α是阿克曼函数的反函数，几乎可以视为常数。

四、扩展应用

并查集常用于解决连通性问题，例如：

• 判断图中是否存在环

• 最小生成树算法（如Kruskal算法）

• 社区检测等

通过上述优化，代码在处理大规模数据时具有较高的效率。