并查集需手写find和union函数：find须路径压缩（递归更新parent[x]），union需先find再合并根节点；初始化用list(range(n))，连通性判断必须用find(a)==find(b)而非parent[a]==parent[b]。
Python 并查集怎么写：用 find 和 union 两函数打底
并查集不是 Python 标准库里的现成类，得自己写；核心就两个操作：find 查根节点，union 合并两棵树。别一上来就套模板，先写清楚这两个函数的逻辑——它们决定了后续所有行为。
常见错误是把 union 写成简单赋值（比如 parent[a] = b），没考虑谁当根、谁挂谁，结果树退化成链表，find 变成 O(n)。正确做法是让小树挂大树（按秩合并），或直接让被查节点指向根（路径压缩）。
实操建议：
-
find必须递归或循环上溯到根，并在返回前重定向父指针（路径压缩的关键一步） -
union先find(a)和find(b)，再比较根是否相同；不同才合并，避免自环 - 初始化用
parent = list(range(n))，别用字典——除非节点 ID 是稀疏非整数
路径压缩为什么必须改 parent 而不只是返回根？
路径压缩不是“查一次根就完事”，而是要永久扁平化访问路径。如果只在 find 里返回根却不更新中间节点的 parent，下次查同一节点还是得走老路，O(n) 问题照旧。
立即学习“Python免费学习笔记（深入）”；
典型错误写法：return find(parent[x])（纯递归返回，没赋值）。正确写法是边回溯边更新：parent[x] = find(parent[x])，或者用循环 + 记录路径后批量更新。
示例（递归版）：
def find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # ← 这行不能少
return parent[x]注意：这行会改变原数组，调试时看到 parent 突然“跳变”别慌，这是压缩生效的表现。
连通性判断：别直接比 parent[a] == parent[b]
刚写完并查集容易犯这个错：以为两个节点父节点相等就代表连通。错——只有根节点相等才算连通，而 parent[a] 可能只是中间父节点，根本不是根。
正确姿势永远是：find(a) == find(b)。哪怕你加了路径压缩，也不能跳过 find 直接比 parent 数组值。
使用场景提醒：
- 图中加边时判断是否成环：加之前
find(u) == find(v)为真，说明已连通，再加就成环 - 处理离线查询（如“此时 a 和 b 是否连通”）：每轮操作后都靠
find判定，不缓存中间parent值 - 性能影响：多一次
find调用，但换来 O(α(n)) 均摊复杂度，远好于 O(n)
按秩合并 vs 路径压缩：可以只选一个，但别漏掉关键细节
路径压缩单独用就能把均摊复杂度压到 O(α(n))，按秩合并（union by rank/size）主要是为了控制树高、辅助分析。实际项目里，光用路径压缩足够；但如果要严格保证单次 find 上限，就得加上按 size 合并。
容易踩的坑：
- 按 size 合并时，更新的是根节点对应的
size值，不是任意节点的 —— 别在union里写size[a] += size[b]，a/b 可能不是根 - 路径压缩后
size不再表示子树大小（因为结构变了），所以按 size 合并只能在union阶段用根的 size 比较，压缩过程不碰size - Python 里用
list存size比用dict快，尤其节点编号连续时
连通性问题本身不依赖树高，但如果你后续要枚举连通分量（比如每个根下拉所有子节点），没按秩合并+路径压缩混用，可能让遍历变慢——这点常被忽略。
