Go中基础并查集应使用struct封装int切片的parent和rank（或size）数组，初始化parent[i]=i，配合路径压缩与按秩/大小合并，避免map、动态扩容及接口转换以保证性能。
Go 里怎么写一个基础并查集结构
直接用 struct 封装父节点数组和秩数组，别用 map 模拟——小范围索引（比如节点编号 0~n-1）下切片性能高、内存连续、无哈希开销。
常见错误是把 parent 初始化成 make([]int, n) 后没重置为 -1 或自身索引，导致 Find 时越界或逻辑错乱。
-
parent[i] = i是最直白的初始化方式（每个节点初始自成一集合） - 如果节点编号稀疏或含负数，才考虑用
map[int]int，但要接受 O(1) 变成均摊 O(log n) 的查找代价 - 加
rank数组做按秩合并，比只靠路径压缩更稳；两者都上，Find均摊接近 O(α(n))
Find 函数为什么一定要路径压缩
不压缩的话，树可能退化成链表，Find 退化为 O(n)，尤其在大量 Union 后反复查根时明显卡顿。
Go 里典型写法是递归+赋值：先递归找到根，再把当前节点父指针直接连到根。别用循环压缩后忘了更新中间节点——那等于白干。
- 错误示范：
for parent[x] != x { x = parent[x] }—— 这只是找根，没改任何parent - 正确压缩：
if parent[x] != x { parent[x] = Find(parent[x]) } - 注意：递归版在超大 n 下有栈溢出风险，生产环境建议改用迭代+两遍扫描（第一遍找根，第二遍回设）
Union 时按秩合并 vs 按大小合并的区别
两者都能控制树高，但语义不同：rank 是「该子树作为根时的最大高度上界」，size 是集合元素个数。Go 里按大小合并更直观，且能顺便支持「查询集合大小」需求。
关键差异在合并方向：按秩合并要求把低秩树挂到高秩树下；按大小合并则是把小集合挂到大集合下。选哪个取决于你后续是否需要维护秩信息。
- 如果只关心连通性，用
size更自然，代码也少一行判断 - 如果之后要扩展「支持撤销 Union」（可持久化并查集），必须用
rank，因为size在合并中不可逆 - Go 中别用
float64或指针存rank——就用int，初始化全 0 即可
LeetCode 上并查集题为什么老超时
不是算法错，大概率是 Go 的接口隐式转换或切片扩容拖慢了。典型坑：用 []interface{} 存节点、用 fmt.Sscanf 解析输入、或每次 Union 都 append 新元素。
真实比赛场景下，输入规模稍大（比如 1e5 节点），这些操作会吃掉 30% 以上时间。
- 输入解析尽量用
bufio.Scanner+strconv.Atoi，别走fmt包 -
parent和size切片必须预分配：make([]int, n)，禁止边跑边 append - 避免在
Find里返回interface{}或包装成方法调用——内联失效，逃逸分析失败
实际写的时候，Find 和 Union 两函数加起来不到 20 行，但初始化顺序、切片零值、递归深度这三处，最容易在压力测试时突然崩。
golang免费学习笔记（深入）：立即使用
在学习笔记中，你将探索golang的核心概念和高级技巧！
