并查集（Union-Find）
一句话说明
并查集专门处理“是否同一集合”和“合并集合”这两件事。
Go 代码
type UnionFind struct {
parent []int
rank []int
}
func NewUnionFind(n int) *UnionFind {
uf := &UnionFind{parent: make([]int, n), rank: make([]int, n)}
for i := 0; i < n; i++ {
uf.parent[i] = i
}
return uf
}
func (uf *UnionFind) Find(x int) int {
if uf.parent[x] != x {
uf.parent[x] = uf.Find(uf.parent[x])
}
return uf.parent[x]
}
func (uf *UnionFind) Union(x, y int) {
rx, ry := uf.Find(x), uf.Find(y)
if rx == ry {
return
}
if uf.rank[rx] < uf.rank[ry] {
uf.parent[rx] = ry
} else if uf.rank[rx] > uf.rank[ry] {
uf.parent[ry] = rx
} else {
uf.parent[ry] = rx
uf.rank[rx]++
}
}
func (uf *UnionFind) Connected(x, y int) bool {
return uf.Find(x) == uf.Find(y)
}关键点
路径压缩和按秩合并是并查集快的原因。