union_find
union_find.go 源码
package disjointset
//并查集代码模板
type UnionFind struct {
parent []int
count int
}
func NewUnionFind(capacity int) *UnionFind {
parent := make([]int, capacity)
for i := 0; i < capacity; i++ {
parent[i] = i
}
return &UnionFind{parent, capacity}
}
func (u *UnionFind) Union(p, q int) {
pSet, qSet := u.Find(p), u.Find(q)
if u.parent[pSet] != qSet {
u.parent[pSet] = qSet
u.count--
}
}
func (u *UnionFind) Find(p int) int {
for p != u.parent[p] {
p = u.parent[p]
}
return p
}
func (u *UnionFind) Connected(p, q int) bool {
return u.Find(p) == u.Find(q)
}
你可能感兴趣的文章
0
赞
热门推荐
-
2、 - 优质文章
-
3、 gate.io
-
6、 golang
-
7、 openharmony