C++怎么实现一个并查集算法？从原理到代码详解

并查集（Disjoint Set Union，常缩写为DSU或UF）用来管理一系列不相交的集合，支持两种核心操作：找到某个元素所属集合的代表元（根节点），以及把两个集合合并成一个。在图论里统计连通块数量、判断加边是否成环、实现Kruskal最小生成树等场景都非常依赖它。用C++实现时，我们通常用两个数组分别记录每个节点的父节点和当前树的近似高度（或大小），再通过两个优化技巧让效率大幅提升。

一、并查集的基本结构设计

最基础的并查集只需要一个整型数组 parent，其中 parent[i] 表示元素 i 的父亲是谁。初始化时每个元素自成一个集合，也就是 parent[i] = i。为了做按秩合并优化，我们再准备一个 rank 数组（或者 size 数组），记录以该节点为根时子树的高度（或节点数）。这样在合并两个集合时，可以把较矮的树挂到较高的树下，避免树退化成链表。

在C++里，我们一般把这些封装成一个类，构造函数接收元素总数 n，用 resize 初始化两个 vector。注意元素编号如果从 0 开始，循环就写到 n-1；如果从 1 开始，则数组大小开到 n+1 更方便。下面给出最朴素版本的骨架，后面再逐步加入优化。

#include <vector>
using namespace std;

class UnionFind {
public:
    vector<int> parent;
    vector<int> rank;

    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;  // 初始每个节点是自己的根
        }
    }
};

二、查找操作与路径压缩

find 函数的目标是返回 x 所在集合的根节点。最简单写法是不断访问 parent[x] 直到 parent[x] == x。但这样容易让树越来越高，后续查找变慢。路径压缩的思想是：在查找过程中，把路径上经过的所有节点直接指向根节点，相当于把长链拍扁。实现时可以用递归，也可以迭代完成后统一赋值。

递归版本非常直观：如果 x 不是根，就先递归找到根，再把 parent[x] 设为根并返回。虽然代码短，但极端深递归可能栈溢出；迭代版本先走到根，再回头把路径上节点全部重连。两种写法时间复杂度在带路径压缩后都接近反阿克曼函数，实际可看作常数。下面给出递归带压缩的实现。

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // 路径压缩：顺手把父节点改成根
    }
    return parent[x];
}

三、合并操作与按秩合并

unionSets（也常叫 unite）负责把包含两个元素的集合合并。正确做法是先分别 find 出各自的根 rootX 和 rootY，如果相同说明已在同一集合，直接返回；否则比较 rank，把 rank 小的根挂到 rank 大的根下面，只有当两者 rank 相等时，随便挂并让被挂的根 rank 加一。这样能严格控制树高，配合路径压缩后几乎不会退化。

如果只做路径压缩不做按秩合并，均摊效率也已经很好；但两者一起用是理论最优组合。需要注意，若用 size 数组代替 rank，逻辑变为把节点少的树合并到节点多的树，同样有效。下面代码展示标准按秩合并写法，并顺带提供判断连通性的 connected 方法。

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]++;  // 高度相同，挂完后根高度+1
    }
}

bool connected(int x, int y) {
    return find(x) == find(y);
}

四、完整示例与简单测试

把前面的内容拼起来就是一个可用的并查集类。我们可以写一段 main 函数，模拟几条边合并，然后查询两点是否连通。这类结构在竞赛和工程里都很常见，比如处理社交网络好友圈、棋盘连通块、动态连通图等。

下面示例中共有 5 个节点，先合并 0-1、1-2，再合并 3-4，最后查询 0 和 2 应该连通，0 和 3 不连通。运行结果符合预期，说明路径压缩与按秩合并都正常工作，整个结构查询合并均为极低成本。

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
    vector<int> parent, rank;
public:
    UnionFind(int n) {
        parent.resize(n);
        rank.assign(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 rx = find(x), ry = find(y);
        if (rx == ry) return;
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else if (rank[rx] > rank[ry]) parent[ry] = rx;
        else { parent[ry] = rx; rank[rx]++; }
    }
    bool connected(int x, int y) { return find(x) == find(y); }
};

int main() {
    UnionFind uf(5);
    uf.unite(0, 1);
    uf.unite(1, 2);
    uf.unite(3, 4);
    cout << uf.connected(0, 2) << endl;  // 输出 1
    cout << uf.connected(0, 3) << endl;  // 输出 0
    return 0;
}

五、常见误区与扩展思路

初学者常把 parent 数组和邻接表搞混，以为并查集存的是图边，其实它只关心每个点的代表元。也有人忘了在 unite 前先 find，直接比较原编号导致合并错误。另一个坑是递归 find 在超大输入下可能爆栈，此时可改成迭代路径压缩。

工程上若元素编号不连续或动态增加，可用 unordered_map 代替 vector 做 parent 映射。若需要删除集合成员，标准并查集不支持，但可用“不删除只标记无效”或离线倒序处理规避。理解清楚这些边界，C++并查集就能稳稳支撑大多数连通性问题。

C++并查集union_find修改时间：2026-08-03 06:18:30