1.设置根节点:
var parent [size]int? //size为实际问题数组长度
for i:=0;i<size;i++{
??????? parent[i]=i?????? //自身为根节点
}
2.查询get:
func get(x int)int{
??????? if x==parent[x]{
??????????????? return x
????????}else{
??????????????? return parent[x]=get(parent[x])?? //路径压缩,向上查询根节点时,把路径经过的节点都?? 挂到根节点下,减少树高
????????}
}
3.合并merge:
秩合并,通过h[]数组记录每个集合的深度,树低的挂在树高下,如果相等都可以,一般优化get即可;
var [size]h []int
func merge(x,y int){
??????? x:=get(x)
??????? y:=get(y)
??????? if h[x]==h[y]{
??????????????? parent[x]=y
??????????????? h[y]++
????????}else if h[x]<h[y]{
??????????????? parent[x]=y
??????????????? h[y]++? //?
????????}else{
??????????????? parent[y]=x
??????????????? h[x]++? //?
????????}
}