unionfind2

Documentation

Index

• type UnionFind2
  • func New(size int) *UnionFind2
  • func (u2 *UnionFind2) GetSize() int
  • func (u2 *UnionFind2) IsConnected(p int, q int) bool
  • func (u2 *UnionFind2) UnionElements(p int, q int)

Types

type UnionFind2

type UnionFind2 struct {
	// contains filtered or unexported fields
}

我们的第二版Union-Find, 使用一个数组构建一棵指向父节点的树 parent[i]表示第一个元素所指向的父节点

func New

func New(size int) *UnionFind2

构造函数

func (*UnionFind2) GetSize

func (u2 *UnionFind2) GetSize() int

func (*UnionFind2) IsConnected

func (u2 *UnionFind2) IsConnected(p int, q int) bool

查看元素p和元素q是否所属一个集合 O(h)复杂度, h为树的高度

func (*UnionFind2) UnionElements

func (u2 *UnionFind2) UnionElements(p int, q int)

合并元素p和元素q所属的集合 O(h)复杂度, h为树的高度