路径压缩需递归，因其利用回溯将查找路径上所有节点直接挂到根；非递归难实现全路径更新，隔代压缩不彻底。
为什么 find 要递归调用自己才能路径压缩
路径压缩的本质，是在一次 find 过程中把整条查找路径上的所有节点“拎起来”，直接挂到根节点下。但如果不递归，就只能改当前节点的父指针，无法知道它的上层节点该指向谁。
比如 parent[4] = 3、parent[3] = 2、parent[2] = 1、parent[1] = 1，调用 find(4) 时：
- 先进 find(3)，再进 find(2)，最后到 find(1) 返回 1；
- 返回途中，parent[2] 被设为 1，parent[3] 被设为 1，parent[4] 也被设为 1。
这一步不能靠循环简单完成（除非用两遍遍历），而递归天然携带“回溯”能力，是最简洁可靠的写法。
- 错误写法：
while parent[x] != x: parent[x] = parent[parent[x]]—— 这只是「隔代压缩」，只压一层，不能保证全部直达根 - 正确写法必须是：
parent[x] = find(parent[x])，且在 return 前赋值 - Python 中递归深度限制一般够用；若数据量超 10⁵，可考虑迭代版（需额外栈模拟）
按秩合并不是必须的，但不加 rank 容易退化成链表
只做路径压缩，find 均摊接近 O(α(n))，但 union 本身不控制树高，多次合并可能让某棵树越长越高。极端情况：连续 union(0,1)、union(1,2)、union(2,3)… 最终形成一条链，首次 find 仍要 O(n) 时间（虽然后续被压缩）。
rank 数组的作用就是记录每棵树的“高度上界”，合并时总把矮树挂到高树下，避免无谓增高：
立即学习“Python免费学习笔记（深入）”；
-
rank初始全为 0，根节点才有效；非根节点的rank值无意义，不用维护 - 当两棵树
rank相等时，任选其一为新根，并对其rank += 1 - 别用
size替代rank—— 按大小合并（union by size）也有效，但逻辑不同，不能混用
Python 实现里 parent 和 rank 的索引必须从 0 开始对齐
几乎所有标准实现都假设元素编号是 0 到 n-1 的整数。如果你的输入是字符串（如 "A"、"B"）或大整数（如 1000001），直接当索引会报 IndexError 或浪费大量内存。
常见应对方式：
- 预处理映射：
id_map = {x: i for i, x in enumerate(unique_items)}，后续所有操作用id_map[x] - 用
dict代替list存parent和rank，动态扩展（但 lose 了 O(1) 随机访问优势） - 如果确定最大编号 ≤ 10⁶，且稀疏度不高，可用
array.array('I', [0]) * max_n省内存
漏掉这步映射，是线上环境跑通本地样例却交题 WA 的高频原因。
union 返回值要不要布尔类型，取决于你是否需要判断是否真的合并了
很多模板里 union(x, y) 返回 True 表示「两个点原本不在同一集合，现在合并成功」，返回 False 表示「本来就在一个集合」。这个信息在连通性计数、最小生成树（Kruskal）、或者去重建边时非常关键。
但如果你只是批量 union 后统一查连通块数量，那这个返回值可以不要——省一次 find 调用（因为已知要先 find(x) 和 find(y)）。
- 要返回值：必须在
rootX == rootY时显式return False，否则默认返回None，容易引发逻辑错误 - 不要返回值：函数末尾不写
return，或统一return None，保持语义清晰 - 别在
union里重复调用find—— 比如先查一遍判断是否同集，再查一遍取根，这是典型冗余
路径压缩和按秩合并看似是“锦上添花”，实际是并查集能扛住 10⁵ 级别查询的底线。漏掉任意一个，在边界数据下都可能从 AC 变成 TLE，而且问题极难复现——因为退化依赖于输入顺序，不是每次运行都触发。
