并查集find应迭代实现路径压缩以避免递归深度限制，必须返回根节点供union判断；union必须按秩合并控制树高，秩是子树最大可能深度上界。
Python 并查集的 find 为什么总写成递归？其实该用路径压缩
不压缩的 find 在多次调用后会退化成链表遍历，时间复杂度从接近 O(1) 拉回 O(n)。递归写法最直观，但 Python 默认递归深度只有 1000，大数据量下容易触发 RecursionError。
更稳妥的是迭代 + 路径压缩：先一路向上找到根，再二次遍历把沿途节点全指到根。
-
find必须返回根节点，不能只“查到了”就完事 —— 后续union依赖这个返回值做判断 - 别在
find里直接改parent[x]，而是在确认根之后统一更新，否则压缩不彻底 - 如果用字典实现（支持非连续整数），
find要先检查 key 是否存在，否则抛KeyError
union 操作里要不要按秩合并？什么时候能省
按秩合并（union by rank）不是可选项，是控制树高的关键。没它，极端情况下并查集就是一条链，find 变慢，整体失去意义。
“秩”不是高度，而是该子树作为根时的**最大可能深度上界**；每次合并都把低秩树挂到高秩树下，秩相等时才给目标根加 1。
立即学习“Python免费学习笔记（深入）”；
- 数组实现时，用单独的
rank列表存；字典实现时，得用另一个字典如rank = {}配合维护 - 如果确定数据规模小（比如
n ）且操作少，可以跳过按秩合并，但别因此删掉 <code>find的路径压缩 - 别把 “按大小合并（union by size）” 和 “按秩合并” 搞混 —— 前者记录子树节点数，也能优化，但逻辑不同，不能混用同一套变量名
初始化写成 list(range(n)) 还是字典推导？看输入类型
输入是连续整数 0~n-1，用 parent = list(range(n)) 最快、最省内存；一旦出现负数、字符串、稀疏 ID（比如用户 ID 是 100001、100005、100010），就必须切到字典。
字典初始化看着灵活，但容易漏初始化：比如只在 union(a, b) 时才把 a 和 b 加进 parent，结果某次 find(x) 传进来一个从未见过的 x，直接 KeyError。
- 安全做法：在首次遇到新节点时自动初始化，例如
if x not in parent: parent[x] = x - 别用
defaultdict(lambda: None)然后靠is None判断 ——find(None)会崩 - 如果输入是字符串 ID，别图省事转成
int(x)再塞数组 —— ID “00123” 转成 int 就丢前导零，还可能越界
LeetCode 上常见 WA：连通分量数统计错在哪
题目让返回“剩余连通分量个数”，很多人直接数 parent[i] == i 的数量，但这是错的：路径压缩后，某些节点的 parent 还没被更新到最新根，导致重复计数。
正确方式只有一种：对每个节点执行一次 find(i)，再用集合去重统计根的数量。
- 别在
union里实时维护 count 变量然后减一 —— 看似高效，但一旦漏了某个合并（比如两个节点已同根），就会多减 - 如果用字典实现，遍历
parent.keys()不够，得遍历所有出现过的节点（比如输入边列表里的全部端点） - 测试时用
[(0,1), (1,2), (3,4)]这种含孤立点的数据，最容易暴露统计 bug
