[]int 是节点编号连续时的唯一合理选择：O(1)随机访问、内存连续、无哈希开销；map[int]int 在 n=1e5 时慢2~3倍且GC压力大。
为什么 parent 用 []int 而不是 map[int]int
节点编号连续（比如 0~n-1）时，[]int 是唯一合理选择：随机访问 O(1)，内存连续，无哈希开销。用 map[int]int 反而慢且多占内存——尤其在 n=1e5 级别时，实测慢 2~3 倍，GC 压力明显上升。
只有两种情况才考虑 map：
- 节点 ID 是字符串（如
"user_123"），必须先做map[string]int映射到稠密整数，否则find里递归没终止条件会 panic - 节点 ID 极其稀疏（如
[1000001, 2000005, 9999999]），但此时得额外维护 ID→index 双向映射，复杂度陡增，不如预处理重编号
常见错误：直接写 parent := make(map[int]int)，然后在 find 里调 find(parent[x]) 却没检查 x 是否在 map 中，导致 key 不存在时返回 0，误连根节点。
find 必须迭代实现，别用递归
Go 没有尾递归优化，深度超过 1000 就可能栈溢出。竞赛或生产环境遇到长链（如 0→1→2→…→9999）时，递归版 find 直接 crash。
立即学习“go语言免费学习笔记（深入）”；
安全的迭代写法（带隔代压缩）：
Golang Uber Dig
下载
使用 uber-go/dig 在 Golang 中实现依赖注入——基于反射容器，提供 Provide/Invoke、dig.In/dig.Out 参数与结果对象，支持命名依赖等
func (uf *UnionFind) find(x int) int {
for uf.parent[x] != x {
uf.parent[x] = uf.parent[uf.parent[x]] // 压缩：跳过父节点
x = uf.parent[x]
}
return x
}关键点：
- 终止条件只能是
uf.parent[x] != x，别写成x != uf.parent[x]（虽等价但易读性差） - 循环内必须更新
x，否则死循环 - 别在
find里碰rank或size——那是union的职责
union 里按 size 合并比按 rank 更实用
两者都能控树高，但 size 语义清晰、调试友好、还顺手支持「查集合大小」需求。按 rank 容易误以为它等于真实高度，结果断言失败——其实 rank 只在合并时更新，不随路径压缩变动。
推荐写法（按 size 合并）：
func (uf *UnionFind) union(x, y int) {
rx, ry := uf.find(x), uf.find(y)
if rx == ry {
return
}
if uf.size[rx] < uf.size[ry] {
uf.parent[rx] = ry
uf.size[ry] += uf.size[rx]
} else {
uf.parent[ry] = rx
uf.size[rx] += uf.size[ry]
}
uf.count--
}注意：
- 必须先
find再比较，否则可能把非根节点当根来挂 -
count减一要在合并成功后执行，别漏 - 初始化
size全为 1，别错写成 0
初始化和输入校验最容易被跳过的坑
三件事不做，后续所有操作都可能错：
-
parent[i] = i必须显式赋值，不能只靠make([]int, n)——后者默认全 0，0 号节点永远指向自己，其余全指向索引 0 - 所有外部输入的节点编号（比如从
bufio.Scanner读进来的）必须校验0 ，否则越界 panic -
rank或size数组也要make同长度，别漏分配
真实场景中，80% 的线上报错来自没做输入范围检查，尤其当输入含空格、负数或超大 ID 时，find(-1) 直接 panic index out of range。
