网上看到的并查集都是一个新的结构体,并且有优化的手段,比如在结构体中携带秩,这样能起到路径压缩的作用。但是在Leetcode刷题时一般可以做一个简单版的并查集来ac,这里记录一下。
func find(parents []int, i int) int {
if parents[i] != i {
parents[i] = find(parents, parents[i])
}
return parents[i]
}
func union(parents []int, i, j int) {
rootX, rootY := find(parents, i), find(parents, j)
if rootX == rootY {
return
}
parents[rootX] = rootY
}
以上就简单定义了并查集的并和查,这样只需要初始化一个数组,然后初始化对应的下标当作值,如果下表跟值相等就说明是一个集合。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。