简单并查集Golang实现
原创
网上看到的并查集都是一个新的结构体，并且有优化的手段，比如在结构体中携带秩，这样能起到路径压缩的作用。但是在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 删除。
评论
登录后参与评论
推荐阅读