C++如何实现并查集算法？路径压缩与按秩合并优化详解

并查集（Union-Find）是一种处理不相交集合合并与查询的数据结构，虽然名字听起来有些学术化，但它的核心思想非常朴素：把每个集合看作一棵树，用父节点数组记录元素之间的归属关系。判断两个元素是否属于同一集合，只需要看它们的根节点是否相同；合并两个集合，只需把一棵树的根挂到另一棵树的根下面。这个结构在连通分量统计、最小生成树的Kruskal算法、动态连通性判断等场景中出现频率极高，也是各大厂面试的常客。本文将用C++从零实现并查集，并重点讲清楚路径压缩与按秩合并这两个关键优化。

并查集的基础实现：父节点数组

最朴素的并查集只需要一个数组parent，初始时每个元素自成一个集合，即parent[i] = i，表示自己是自己的根。查找操作find(x)沿着父指针一路向上，直到遇到parent[x] == x的节点，该节点就是所在树的根。合并操作unionSets(x, y)则先分别找到二者的根，再把其中一个根的父指针指向另一个根。

#include <iostream>
#include <vector>

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

    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; ++i)
            parent[i] = i;  // 初始时每个元素自成一个集合
    }

    // 查找根节点
    int find(int x) {
        while (parent[x] != x)
            x = parent[x];
        return x;
    }

    // 合并两个集合
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY)
            parent[rootX] = rootY;
    }
};

这个版本写起来最简单，但存在明显缺陷：如果每次合并都把大树挂到小树下面，或者按链式顺序合并，树会退化成一条长链。此时find操作的最坏时间复杂度达到O(n)，n次操作下来总复杂度退化为O(n²)，在数据量大时完全不可接受。

举个直观的例子，依次执行unionSets(0,1)、unionSets(1,2)、unionSets(2,3)……由于每次都是把前面的根挂到后面的根上，最终0号节点要访问n个节点才能找到根。这正是需要优化的地方，优化方向有两个：一是让查找路径变短（路径压缩），二是让树本身长得更矮（按秩合并）。

路径压缩：查找的同时拍扁树结构

路径压缩的思路是：在执行find(x)的过程中，把从x到根路径上的所有节点，直接全部挂到根下面。这样一来，即使某次查找走了很长的路径，之后这些节点的查找都会变成一步到位。实现上用递归写法极其简洁，一行代码就能完成。

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);  // 递归找到根后，把当前节点直接挂到根上
    return parent[x];
}

递归版本虽然优雅，但在元素规模达到百万级时，如果树恰好很深，递归可能导致栈溢出。因此工程中更推荐迭代写法：先走一遍找到根，再走第二遍把路径上所有节点的父指针改写为根。

int find(int x) {
    int root = x;
    while (parent[root] != root)
        root = parent[root];      // 第一遍：找到根
    while (parent[x] != root) {
        int next = parent[x];
        parent[x] = root;          // 第二遍：路径压缩
        x = next;
    }
    return root;
}

还有一种折中方案叫路径减半，即每走一步就把当前节点挂到祖父节点上，只需一遍遍历即可完成，压缩效果略弱但实现更轻量。无论哪种写法，路径压缩的核心收益是：树的高度会随着操作次数增加而快速下降，绝大多数节点最终都紧贴在根附近。

按秩合并：控制树的高度增长

按秩合并（Union by Rank）解决的是合并策略的随意性问题。所谓秩，可以近似理解为树的高度上界。合并两棵树时，总是把秩较小的树挂到秩较大的树下面，这样合并后的树高度不会超过较大那棵树的高度加一。只有当两棵树秩相同时，合并后新根的秩才需要加一。

与之类似的还有按大小合并，即把节点数少的树挂到节点数多的树下面，两种策略的效果接近，这里以按秩合并为例给出完整实现。

class UnionFind {
public:
    std::vector<int> parent, rank_;

    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];
    }

    bool unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY)
            return false;  // 已在同一集合，合并失败
        if (rank_[rootX] < rank_[rootY])
            parent[rootX] = rootY;
        else if (rank_[rootX] > rank_[rootY])
            parent[rootY] = rootX;
        else {
            parent[rootY] = rootX;
            rank_[rootX]++;  // 秩相同时，新根的秩加一
        }
        return true;
    }
};

注意这里成员变量命名为rank_是为了避免与std::rank等名字产生冲突，加上下划线后缀是常见的工程习惯。还有一个细节：使用了路径压缩后，秩就不再精确等于树的真实高度，但它依然是一个有效的合并依据，不影响复杂度结论。

把两种优化结合起来，单次操作的均摊时间复杂度为O(α(n))，其中α是阿克曼函数的反函数，增长极其缓慢，在可观测的宇宙规模的数据量下α(n)不超过4，因此实践上可以当作常数时间看待。这也是并查集在动态连通性问题中近乎无可替代的原因。

实战案例：统计朋友圈数量

理论讲完了，用一个经典题目来落地。假设有n个学生，给定一个二维矩阵isConnected，其中isConnected[i][j] = 1表示第i和第j个学生直接认识，间接认识也算同一个朋友圈，求朋友圈的总数。这类连通分量计数问题正是并查集的拿手好戏。

#include <iostream>
#include <vector>

class UnionFind {
public:
    std::vector<int> parent, rank_;
    int count;  // 记录当前集合数量

    UnionFind(int n) : count(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]++; }
        count--;  // 每合并一次，集合数减一
    }
};

int findCircleNum(std::vector<std::vector<int>>& isConnected) {
    int n = isConnected.size();
    UnionFind uf(n);
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (isConnected[i][j] == 1)
                uf.unite(i, j);
    return uf.count;
}

int main() {
    std::vector<std::vector<int>> matrix = {
        {1, 1, 0},
        {1, 1, 0},
        {0, 0, 1}
    };
    std::cout << findCircleNum(matrix) << std::endl;  // 输出 2
    return 0;
}

这个实现里的小技巧是维护一个count变量记录集合数量：初始化为n，每次成功合并就减一，最后无需遍历统计不同根的个数，直接返回即可。矩阵是对称的，所以内层循环从j = i + 1开始，避免重复合并，把遍历量减少了一半。

类似的题目还有很多变体，比如判断图中加入若干条边后是否形成环（合并前先查根，若根相同则成环）、岛屿数量问题（把网格坐标线性化后套用并查集）、Kruskal最小生成树（按边权排序后用并查集避免选入成环的边）。掌握本文的模板后，这些题目都只是换汤不换药。

常见坑点与工程建议

写并查集时有几个容易踩的坑值得提醒。第一，find操作必须真正找到根为止，不要误写成判断parent[x] == y就返回，那样比较的是父节点而非根节点。第二，合并时一定要对根节点操作，如果直接parent[x] = y，可能把已经合并过的一部分节点丢掉。第三，如果需要按集合遍历元素，可以在并查集外面再维护一个unordered_map<int, vector<int>>，以根为键聚合成员。

另外在空间敏感的场景下，可以视情况只采用路径压缩或只采用按秩合并。单用按秩合并不做路径压缩，单次操作是O(log n)；单用路径压缩的均摊复杂度是O(log n)级别，虽然理论上略逊于两者结合，但省掉了一个数组，实测差距往往可以忽略。算法竞赛中流行一种更极端的写法：直接parent[find(y)] = find(x)配合路径压缩，代码最短，性能也完全够用。理解了原理之后，选择哪种写法就看具体场景对代码可读性和极限性能的要求了。

并查集C++数据结构路径压缩修改时间：2026-09-10 19:24:43