并查集

基础与数据结构

说明

维护元素所属的连通集合；路径压缩与按秩合并使操作接近常数时间。

分析

每个集合用一个代表根节点表示，Find 沿 parent 链寻找它。路径压缩缩短以后查询的路径，按秩合并避免树过高。

Union(0,2)先找根，再把2挂到0下面，二者Find相等。路径压缩会改写父指针，Find不一定是只读操作；秩控制合并方向，不是压缩后的精确高度，近常数指均摊反阿克曼复杂度。

查看图表代码

适用前提与边界

它擅长动态合并与连通性查询，但普通并查集不支持高效拆分已合并集合。 元素编号必须落在0到n-1；重复Union不改变集合，普通路径压缩实现不支持直接撤销合并。

示例输入与调用

groups := NewDSU(3)
	groups.Union(0, 2)
	fmt.Println(groups.Find(0) == groups.Find(2))

运行输出

true

完整 Go 示例

package main

import "fmt"

type DSU struct{ parent, rank []int }

func NewDSU(n int) *DSU {
	d := &DSU{make([]int, n), make([]int, n)}
	for i := range d.parent {
		d.parent[i] = i
	}
	return d
}
func (d *DSU) Find(x int) int {
	if d.parent[x] != x {
		d.parent[x] = d.Find(d.parent[x])
	}
	return d.parent[x]
}
func (d *DSU) Union(a, b int) {
	a, b = d.Find(a), d.Find(b)
	if a == b {
		return
	}
	if d.rank[a] < d.rank[b] {
		a, b = b, a
	}
	d.parent[b] = a
	if d.rank[a] == d.rank[b] {
		d.rank[a]++
	}
}

func main() {
	groups := NewDSU(3)
	groups.Union(0, 2)
	fmt.Println(groups.Find(0) == groups.Find(2))
}