最高效的是用[]int实现带路径压缩和按秩合并的数组版union-find：parent[i]==i表示根节点，find递归压缩路径，union按rank比较避免退化，初始化parent[i]=i、rank全0。
Go 语言实现并查集（Union-Find）不需要第三方库，核心就两个操作：Find 和 Union，但直接写容易踩内存和性能坑——比如用切片做 parent 数组时忘了路径压缩，或用指针结构体导致 GC 压力大。
怎么写一个带路径压缩的数组版 Union-Find
最常用、最高效的方式是用 []int 存 parent 索引，配合路径压缩 + 按秩合并（rank）。不推荐用结构体嵌套指针，那会引入不必要的间接访问和 GC 开销。
关键点：
-
parent[i] == i表示i是根节点 -
Find必须递归或迭代做路径压缩：把沿途所有节点直接连到根 -
Union比较rank决定谁当新根，避免树退化成链表 - 初始化时
rank全为 0，parent[i] = i
示例片段：
type UnionFind struct {
parent []int
rank []int
}
func NewUnionFind(n int) *UnionFind {
parent := make([]int, n)
rank := make([]int, n)
for i := 0; i
<h3>为什么不能省略 rank 或只做路径压缩</h3>
<p>只做路径压缩（无 rank）在极端 case 下仍可能让树高达到 O(log n)，而按秩合并能保证单次 <code>Find</code> 均摊接近 O(α(n))；反过来，只按秩不压缩，查询会退化成 O(log n)。两者缺一不可。</p>
<p>常见误写：</p>
- 在
Union中漏掉if uf.rank[px] == uf.rank[py]的自增判断 → 后续合并失去平衡性 -
Find写成非递归但没更新父节点（只返回根，没压缩路径）→ 失去均摊优势 - 用
map[int]int存 parent，键是任意整数（如离散化 ID）→ 性能差且易忘初始化，默认值 0 会被误认为有效根
处理非连续或负数 ID 怎么办
原生数组版只支持 0..n-1。如果输入是字符串、负数或稀疏 ID（如 1000001, 9999999），别硬套数组——先做离散化映射。
Go语言（Golang）1.26.0
下载
Go语言（Golang）1.26.0版本提供 Go 官方 Windows amd64 MSI 安装包下载入口，版本号 1.26.0，可用于旧项目维护、兼容性测试和指定版本开发环境配置。
安全做法：
- 收集所有出现的 ID 到 slice，排序去重，用
sort.Search查下标 - 或用
map[any]int做 id → index 映射，再把 index 交给数组版UnionFind - 避免直接在
map[int]int上实现 Find/Union —— 没有 rank 控制，无法保证复杂度，且 map 查找本身是 O(1) 平摊但常数大
例如：
ids := []int{105, -3, 999999}
sort.Ints(ids)
ids = unique(ids) // 去重
// 然后用 map[int]int{105: 0, -3: 1, 999999: 2} 做转换
并发场景下怎么安全使用
UnionFind 本身不是线程安全的。多个 goroutine 同时调用 Union 或 Find 会引发数据竞争。
简单方案：
- 用
sync.Mutex包一层，适合读多写少、总操作数不大的情况 - 如果图是静态的（只构建一次，之后只读），可预先计算连通分量，用
map[int]int缓存每个节点的根，之后并发读无锁 - 不要试图给每个
parent元素加atomic——Find是多步依赖，原子操作无法覆盖路径压缩逻辑
错误示范：atomic.LoadInt32(&uf.parent[x]) 只读一个值，但 Find 需要写回压缩后的根，必须整体加锁。
路径压缩和按秩合并的组合看似简单，但漏掉任一环节，实际运行中在大数据量下就会明显变慢；而 map 实现看似灵活，反而在高频调用时成为瓶颈。选数组 + 离散化 + 适度加锁，是 Go 里最稳的落地方式。
golang免费学习笔记（深入）：立即使用
在学习笔记中，你将探索golang的核心概念和高级技巧！
