C++ 并查集算法详解：原理、操作与路径压缩实现

Ada

发布时间：2026-10-16| 6人浏览过

原创

并查集是一种用于管理元素所属集合的数据结构，支持查找（Find）和合并（Union）两种核心操作。本文将介绍在 C++ 中如何初始化并查集数组，通过递推或递归实现高效查找，执行集合合并，并利用路径压缩技术优化性能，使查询接近常数时间复杂度。

第1步：并查集的初始化

并查集通常使用一维数组 father[N] 来实现，其中 father[i] 表示元素 i 所在集合的父亲节点。初始状态下，每个元素各自构成一个独立的集合，其父亲节点即为自身。初始化代码如下：

int father[N];
// 初始化所有元素的父节点为自己
for(int i = 1; i <= N; i++){
    father[i] = i;
}

初始化完成后，数组 father 的结构反映了所有元素均处于独立集合的状态。

第2步：实现查找操作（Find）

查找操作用于确定某个元素所属集合的根节点。根据树形结构规定，同一集合中仅存在一个根节点（即 father[root] == root）。查找过程即从当前节点不断向上回溯至根节点。支持递推和递归两种写法：

递推实现

通过循环不断将当前节点更新为其父节点，直到找到根节点为止：

// findFather 返回元素 x 所在集合的根结点
int findFather(int x){
    while(x != father[x]){    // 若非根结点，继续循环
        x = father[x];        // 获得自己的父亲结点
    }
    return x;
}

递归实现

若当前节点是根节点则直接返回，否则递归查找其父节点的根节点：

int findFather(int x){
    if(x == father[x]) return x;    // 找到根结点，返回
    else return findFather(father[x]); // 递归判断父结点是否为根
}

第3步：执行集合合并（Union）

合并操作旨在将两个不同集合整合为一个。基本思路是先分别查找两元素所属集合的根节点，若根节点不同，则将其中一个根节点的父节点指向另一个根节点。代码示例如下：

void Union(int a, int b){
    // 将 a 所在集合的根节点的父节点指向 b 所在集合的根节点
    father[findFather(a)] = findFather(b); 
}

注意：在执行合并前，建议先通过 findFather() 检查两元素是否已在同一集合中，以避免冗余操作或逻辑错误。

第4步：路径压缩的必要性

在最坏情况下，并查集的树形结构可能退化为链状，导致查找操作的时间复杂度退化至 O(N)。路径压缩是一种有效的优化手段，其核心思想是在查找过程中，将所有经过节点的父节点直接指向根节点，从而“压扁”树的高度。

图注：并查集在未优化前的树形结构示意图

第5步：实现路径压缩

路径压缩可以在查找函数 findFather 内部自然完成。当递归回溯时，将路径上所有节点的父指针直接重定向至根节点。具体效果如下图所示：

图注：压缩前的节点层级关系，例如 father[3]=2, father[2]=1

图注：压缩后的状态，所有非根节点直接指向根节点，例如 father[3]=1, father[2]=1

优化后的查找代码如下：

int findFather(int x){
    // 如果当前节点不是根节点，则递归查找其父节点的根节点
    // 并将找到的根节点直接赋给当前节点的父节点（路径压缩）
    if(father[x] != x) father[x] = findFather(father[x]);
    return father[x];
}

逻辑解析：