C++实现带路径压缩的并查集优化 _ 集合连通性判定与效率【源码】-C++-PHP中文网

路径压缩需递归实现并确保每层返回前更新父节点，或迭代时缓存路径统一修改；与按秩合并共存时rank仅用于union决策，不反映压缩后高度。

c++实现带路径压缩的并查集优化 _ 集合连通性判定与效率【源码】

为什么路径压缩不能只靠一次 find 就完事

路径压缩的核心目标是让后续 find 操作接近 O(1)，但很多人误以为只要在 find 里写一句 parent[x] = find(parent[x]) 就万事大吉。问题在于：如果递归返回时没正确更新当前节点的父节点，或者用了非递归写法却忘了回溯修改，压缩就失效了。更隐蔽的是，和按秩合并（unionByRank）混用时，若先做了路径压缩再调用 union，可能破坏秩信息——因为压缩会改变树高，但 rank 数组并未同步更新。

实操建议：

必须用递归版 find 实现压缩，确保每层返回前都重置 parent[x]
若坚持迭代写法，需额外缓存访问路径（如用 std::vector 存下从 x 到根的所有节点），再统一指向根
按秩合并与路径压缩可共存，但 rank 仅用于 union 决策，不反映压缩后的实际高度，因此无需、也不应被路径压缩修改

带路径压缩的 find 函数怎么写才不出错

最简且健壮的递归实现是：int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }。注意三点：一是必须用赋值表达式 parent[x] = find(...)，而非先调用再赋值；二是不能写成 return parent[x] = parent[x] == x ? x : find(parent[x]);，这会因运算符优先级导致逻辑错误；三是若用 std::vector<int></int> 存 parent，务必保证索引合法（常见坑：用负数或越界下标调用 find）。

示例中易错写法对比：

int find_bad(int x) {
    if (parent[x] != x) {
        int root = find_bad(parent[x]);
        parent[x] = root;  // ✅ 正确，显式赋值
        return root;
    }
    return x;
}
int find_broken(int x) {
    if (parent[x] != x) {
        return parent[x] = find_broken(parent[x]);  // ✅ 等价于上面，简洁
    }
    return x;
}
// ❌ 错误：下面这行会先算 parent[x] == x ? x : ...，再把结果赋给 parent[x]
// return parent[x] = (parent[x] == x ? x : find_broken(parent[x]));

初始化、union 和 find 的配合要点

并查集不是三个独立函数，而是一套状态协同机制。初始化时，parent[i] = i 是必须的，但常被忽略的是：若集合元素编号不连续（比如只用 1,3,5,7），就不能简单用 vector 下标遍历，得维护一个活跃节点集合或用 std::map。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

实操建议：

unionSets(int a, int b) 必须先 find(a) 和 find(b)，再比较根是否相同——否则会把同一集合内节点重复 union，浪费且可能干扰 rank
路径压缩只发生在 find 中，union 过程中绝不直接修改 parent（除最终的根指向外），否则压缩失效
若需频繁查询连通性（如判断两点是否同属一集合），直接用 find(a) == find(b)，别缓存中间结果，因为路径压缩会让后续 find 更快