并查集效率低主因是未启用路径压缩；优化方式包括：一、递归路径压缩；二、迭代路径压缩；三、按秩合并+路径压缩；四、引用计数判定压缩效果；五、模板化泛型实现。

如果您在实现 C++ 并查集（Union-Find）结构时发现合并与查询操作效率偏低，可能是由于未启用路径压缩优化，导致树高增长、查找时间退化为线性。以下是针对带路径压缩的并查集算法的多种优化实现方式及其判定逻辑说明：

一、递归路径压缩实现

该方法在 find 操作中递归回溯时将沿途所有节点直接挂载到根节点下，显著降低后续查找深度。其核心在于利用递归返回过程重写 parent 数组。

1、定义 int 类型数组 parent，初始化 parent[i] = i；

2、定义 find 函数：若 parent[x] != x，则执行 parent[x] = find(parent[x]) 并返回 parent[x]；

3、union 操作中先 find(x) 与 find(y)，若根不同则将一方根指向另一方根。

二、迭代路径压缩实现

避免递归调用栈开销，在 find 中先遍历至根节点，再二次遍历将路径上所有节点 parent 设为根。适用于栈空间受限或需严格控制递归深度的场景。

1、在 find 函数内声明变量 root = x，循环执行 root = parent[root] 直至 parent[root] == root；

2、再次从 x 开始遍历，对每个当前节点 curr 设置 parent[curr] = root，并更新 curr = parent[curr]；

3、返回 root 作为最终根节点。

三、按秩合并 + 路径压缩联合优化

单独路径压缩虽改善查询，但合并可能造成树高激增；引入 rank 数组记录各树近似高度，仅将矮树根指向高树根，抑制整体深度增长，与路径压缩形成互补。

1、额外声明 vector rank，初始化全为 0；

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

2、find 使用递归路径压缩；

3、union 操作中比较 find(x) 与 find(y) 的 rank 值：rank[rx] rank[ry] 时令 parent[ry] = rx；相等时任选其一并令对应 rank 加 1。

四、基于引用计数的路径压缩判定逻辑

为验证路径压缩是否生效，可在 find 返回前插入判定逻辑：统计压缩前后路径长度变化。该逻辑不参与主流程，仅用于调试与性能分析。

1、在 find 函数入口记录初始深度变量 depth = 0，沿 parent 向上计数直至根；

2、执行路径压缩后再次计算当前节点到根的距离；

3、若压缩后距离 严格小于 2，则表明路径压缩已将该节点直连根节点。

五、模板化泛型实现与类型安全判定

使用 template 将并查集泛化为支持任意可哈希类型的结构，通过 std::unordered_map 替代固定数组索引，适配非连续整数键。此时路径压缩有效性依赖于 map 查找稳定性及引用一致性。

1、声明 unordered_map parent，初始化时 insert({x, x})；

2、find 函数中对 key 存在性校验：若 parent.find(x) == parent.end()，则立即插入 {x, x} 并返回 x；

3、递归压缩时确保每次 parent[x] 已存在且非空，避免未定义行为。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！