Go 并查集

发布时间:2024年01月12日

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]++? //?

????????}

}

文章来源:https://blog.csdn.net/zb_915574747/article/details/135548403
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。