C++怎么实现一个并查集算法_C++算法设计与并查集实现_技术教程

并查集通过路径压缩和按秩合并高效处理集合合并与查询，支持连通性判断、求连通分量等操作，常用于Kruskal算法、岛屿问题等场景。

并查集（Union-Find）是一种高效处理不相交集合合并与查询的数据结构，常用于解决连通性问题，比如判断图中两个节点是否连通、求连通分量个数等。在 C++ 中实现并查集非常直观，核心操作包括查找（find）和合并（union）。通过路径压缩和按秩合并优化，可以将时间复杂度接近常数级别。

基本结构与初始化

并查集通常用一个数组 parent 来表示每个元素的父节点，初始时每个元素的父节点是自己，表示各自独立成一个集合。

还可以引入 rank 数组来记录每棵树的“秩”（近似高度），用于优化合并操作。

class UnionFind {
public:
    vector parent;
    vector rank;

    // 构造函数，初始化 n 个独立元素
    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 unite(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]++;
        }
    }

    // 判断两个元素是否属于同一集合
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

关键优化：路径压缩与按秩合并

这两个优化策略显著提升并查集效率：

路径压缩：在 find 过程中，把沿途所有节点直接连到根节点，降低后续查找成本。
按秩合并：合并时尽量让较矮的树接在较高的树下，避免生成过深的树，控制整体高度。

经过这两种优化后，单次操作的平均时间复杂度接近 O(α(n))，其中 α 是阿克曼函数的反函数，增长极慢，可视为常数。

实际应用场景举例

假设要判断无向图中边的连接是否会形成环，可以用并查集逐条处理边：

#include 
#include 
using namespace std;

int main() {
    int n = 5;
    UnionFind uf(n);

    // 添加边 (0,1), (1,2), (3,4)
    uf.unite(0, 1);
    uf.unite(1, 2);
    uf.unite(3, 4);

    cout << "0 和 2 连通吗？" << (uf.connected(0, 2) ? "是" : "否") << endl;  // 是
    cout << "0 和 3 连通吗？" << (uf.connected(0, 3) ? "是" : "否") << endl;  // 否

    uf.unite(2, 3);
    cout << "0 和 4 连通了吗？" << (uf.connected(0, 4) ? "是" : "否") << endl;  // 是

    return 0;
}