C++怎么实现并查集？高效集合合并教程详解

并查集（Union-Find）是一种管理不相交集合的数据结构，核心功能有两个：一是查询某个元素所属的集合，二是合并两个不相交的集合。在C++中实现并查集，通常会用数组来存储每个元素的父节点，通过递归或迭代的方式完成查找和合并操作，优化后可以达到接近常数的时间复杂度。

并查集的基础实现

1. 初始化

初始化时，每个元素单独构成一个集合，父节点指向自己，同时可以初始化一个秩数组（记录集合的高度或大小）用于后续优化。

#include <vector>
using namespace std;

class UnionFind {
private:
    vector<int> parent; // 存储每个元素的父节点
    vector<int> rank;   // 存储集合的秩，用于按秩合并优化
public:
    // 初始化n个元素，每个元素的父节点是自己，秩初始化为0
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
};

2. 查找操作

查找操作的作用是找到某个元素所在集合的根节点，基础版本是递归查找父节点直到根节点，优化版本会加入路径压缩，让查找路径上的所有节点直接指向根节点，减少后续查找的时间。

// 基础查找：递归找到根节点
int find(int x) {
    if (parent[x] != x) {
        return find(parent[x]);
    }
    return x;
}

// 优化查找：路径压缩，让x到根节点的路径上所有节点直接指向根节点
int findWithPathCompression(int x) {
    if (parent[x] != x) {
        parent[x] = findWithPathCompression(parent[x]); // 递归压缩路径
    }
    return parent[x];
}

3. 合并操作

合并操作是将两个元素所在的集合合并为一个集合，基础版本是直接把一个集合的根节点指向另一个集合的根节点，优化版本会结合按秩合并，把秩小的集合合并到秩大的集合上，避免树的高度过高。

// 基础合并：把x所在集合合并到y所在集合
void unionSet(int x, int y) {
    int rootX = findWithPathCompression(x);
    int rootY = findWithPathCompression(y);
    if (rootX != rootY) {
        parent[rootX] = rootY;
    }
}

// 优化合并：按秩合并，把秩小的集合合并到秩大的集合
void unionSetWithRank(int x, int y) {
    int rootX = findWithPathCompression(x);
    int rootY = findWithPathCompression(y);
    if (rootX == rootY) {
        return; // 已经在同一集合，不需要合并
    }
    // 按秩合并，秩小的树合并到秩大的树
    if (rank[rootX] < rank[rootY]) {
        parent[rootX] = rootY;
    } else if (rank[rootX] > rank[rootY]) {
        parent[rootY] = rootX;
    } else {
        // 秩相等时，任意合并，合并后秩加1
        parent[rootY] = rootX;
        rank[rootX]++;
    }
}

完整的高效并查集实现

结合路径压缩和按秩合并两种优化，我们可以实现一个时间复杂度接近O(1)的高效并查集，完整代码如下：

#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 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 isConnected(int x, int y) {
        return find(x) == find(y);
    }
};

// 测试示例
int main() {
    UnionFind uf(10); // 初始化10个元素，编号0-9
    uf.unite(1, 2);
    uf.unite(2, 3);
    uf.unite(4, 5);
    cout << "1和3是否连通：" << (uf.isConnected(1, 3) ? "是" : "否") << endl;
    cout << "1和4是否连通：" << (uf.isConnected(1, 4) ? "是" : "否") << endl;
    uf.unite(3, 4);
    cout << "合并后1和4是否连通：" << (uf.isConnected(1, 4) ? "是" : "否") << endl;
    return 0;
}

并查集的应用场景

并查集的常见应用场景包括：判断图的连通分量数量、动态连通性问题（比如网络连接判断）、最小生成树算法中的Kruskal算法等。在这些场景中，并查集的高效合并和查询特性可以大幅降低代码的复杂度，提升运行效率。

C++并查集集合合并Union_Find修改时间：2026-06-09 03:36:30