路径压缩是提升并查集查找性能的关键优化手段，包括递归压缩、迭代压缩、按秩合并联合优化、可回滚变体及泛型模板化实现五种方案。
如果您在实现 C++ 并查集（Union-Find）结构时发现合并与查询操作效率偏低，且希望在不改变接口的前提下显著降低树高、提升查找性能，则路径压缩是一种关键优化手段。以下是实现带路径压缩并查集的多种技术方案及其对应判定逻辑与源码细节：
一、基于递归路径压缩的并查集实现
该方法在 find 操作中递归回溯时将沿途所有节点直接挂载到根节点下，使后续查找时间趋近常数。其核心在于利用递归返回过程完成指针重定向，无需额外空间记录路径。
1、定义 parent 数组，初始化每个元素 parent[i] = i；
2、实现 find 函数：若 x 不等于 parent[x]，则执行 parent[x] = find(parent[x]) 并返回 parent[x]；
3、实现 unionSet 函数：先调用 find 获取两节点根，若根不同则将一棵子树根指向另一棵根；
4、在每次 find 调用后，所有被访问过的中间节点 parent 值均被更新为最终根节点索引。
二、基于迭代路径压缩的并查集实现
该方法避免递归调用栈开销，使用显式循环定位根节点后再遍历路径进行扁平化，适合栈空间受限或需严格控制调用深度的嵌入式场景。
1、定义 parent 数组和 size 数组（用于按秩合并）；
2、在 find 函数中，先用 while 循环找到根节点 root；
3、再次遍历从 x 到 root 的路径，将每个节点 parent 设置为 root；
4、第二次遍历必须在获取 root 后立即执行，否则路径信息将因 parent 修改而丢失。
三、结合按秩合并与路径压缩的联合优化实现
仅路径压缩无法保证单次 union 时间上限，引入按秩合并（union by rank）可将树高严格限制在 O(log n)，与路径压缩叠加后理论复杂度可达反阿克曼函数级别。
1、维护 rank 数组，初始值全为 0；
2、find 仍采用递归路径压缩方式；
3、unionSet 中比较两根节点 rank 值：rank 小者根指向 rank 大者；若相等，则任选其一作为新根并将其 rank 加 1；
4、rank 仅在两子树高度相等时才递增，且绝不随路径压缩而更新。
四、支持撤销操作的可回滚并查集变体
当需要在图连通性动态变化中支持“回退一步”能力时，标准路径压缩会破坏历史结构，因此须改用仅压缩至父节点的半路径压缩策略，并记录操作日志。
1、定义 parent 数组与 opStack 栈，用于存储 (x, old_parent) 对；
2、find 实现为：若 parent[x] ≠ x，则将 x 的 parent 设为其父节点的 find 结果，同时压栈原始 parent[x]；
3、提供 rollback 接口：弹出栈顶操作并恢复 parent[x] 值；
4、此版本禁止完全路径压缩，否则无法精确还原任意中间状态。
五、模板化泛型并查集实现（支持任意键类型）
为适配非整数索引（如字符串、pair 等），需借助 std::map 或 std::unordered_map 映射键到内部整型 ID，并确保 find 和 unionSet 对键的语义一致性。
1、声明 map
2、首次访问键 k 时分配新 id 并初始化 parent[id] = id；
3、所有 find/union 操作均作用于映射后的整型 id；
4、keyToId 必须在所有 find 调用前完成初始化，运行时插入新键需同步扩展 parent 容量。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
