用 parent 数组+路径压缩而非 list 是因前者均摊时间达 O(α(n))，后者 find 为 O(n)；路径压缩需递归或迭代更新整条路径，否则退化；按秩合并中 rank 是上界估计值，仅根秩相等时才+1；带权并查集需 dist 数组同步更新；Python 中应避免字典和递归，用 list 和循环提升性能。
为什么不用 list 而要用 parent 数组 + 路径压缩？
直接用 list 存每个节点的根会导致每次 find 都是 O(n)；而用数组索引映射节点（如节点 0~n-1），配合路径压缩，能让均摊时间接近 O(α(n))。实际中，parent[i] = i 初始化后，find 过程中把沿途所有节点直接连到根，下次再查就一步到位。
常见错误是只改了当前节点的父节点，没递归更新整条路径——结果压缩不彻底，性能掉回 O(log n) 甚至更差。
-
find必须写成递归或带循环+记录路径的迭代，不能只改一层 - 初始化时确保
parent = list(range(n))，别用[i for i in range(n)]这种低效写法 - 如果节点编号不连续（比如是字符串或大整数），先做离散化映射到 0~k-1 再建数组
union 操作里按秩合并（union by rank）怎么写才不翻车？
单纯按大小合并（union by size）或按深度合并（union by rank）都能保证树高 ≤ log n，但“秩”在这里不是真实深度，而是上界估计值——它只在两棵树秩相等时才+1，否则不更新。误把 rank 当作实时深度去维护，反而会破坏性质。
典型错误：在 union(a, b) 里没判断谁的根更深，直接让 a 的根挂到 b 的根下，导致树退化。
立即学习“Python免费学习笔记（深入）”；
- 必须先
find(a)和find(b)得到根，再比较它们的rank - 只在两个根秩相等时，才给新根的
rank += 1；否则不碰rank数组 - 推荐用
rank（而非size），因为实现更轻量，且和路径压缩兼容性更好
如何支持带权并查集（如维护到根的距离）？
普通并查集只能回答“是否连通”，但加一个 dist 数组就能支持“两点间相对距离”查询——比如在食物链、差分约束问题里必须用到。关键在于：路径压缩时，dist[i] 要叠加子节点到父节点、父节点到根的距离。
容易踩的坑是 find 里只更新 parent[i]，忘了同步修正 dist[i]；或者在 union 时用错公式，导致符号或偏移出错。
-
find中递归调用后，用dist[i] += dist[parent[i]]更新（前提是dist[i]原本存的是到直接父节点的距离） -
union(a, b, w)表示 “a 到 b 的距离为 w”，需推导出根之间应满足的关系式，再更新dist[root_a] - 所有涉及
dist的操作，必须和parent更新严格同步，顺序不能颠倒
Python 实现时哪些细节影响性能？
纯 Python 实现并查集，瓶颈往往不在算法逻辑，而在对象模型和内存访问模式。比如用字典代替数组来支持非整数节点，看似灵活，但哈希开销会让 find 慢 3–5 倍；又比如频繁创建新列表、用 set 统计连通分量数量，都会拖慢整体速度。
真正高频场景（如处理 10⁵ 条边）下，几个硬核建议：
- 坚持用
list管理parent和rank，哪怕要预估最大节点数 - 避免在
find中使用self.parent[i] = self.find(self.parent[i])这种写法——Python 递归调用开销大，改用 while 循环+路径记录更稳 - 连通分量计数不要每次遍历所有节点，维护一个
count变量，在每次成功union后减 1
路径压缩和按秩合并的组合效果，在 Python 里需要实打实写对才能体现；写错一行，就退回 O(n) 级别。
