Feb 23, 2021
Documentation
Overview ¶
Package DisjointSet provides a disjoint-set data structure with fixed size.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type DisjointSet ¶
type DisjointSet struct {
// contains filtered or unexported fields
}
DisjointSet implements a disjoint-set data structure with fixed size.
Each element is represented by a 0-based array index.
Also known as union-find or merge-find set. See https://en.wikipedia.org/wiki/Disjoint-set_data_structure.
func New ¶
func New(size int) DisjointSet
New constructs new DisjointSet of `size` elements each in its own set.
func (DisjointSet) Disjoint ¶
func (d DisjointSet) Disjoint(i, j int) bool
Disjoint returns true if i-th and j-th elements are in different sets.
func (*DisjointSet) Merge ¶
func (d *DisjointSet) Merge(i, j int) bool
Merge merges i-th and j-th elements' sets.
If they are in the same set, does nothing and returns false. Else, does the merges and returns true.
This is the only allowed mutation.
func (DisjointSet) RootOf ¶
func (d DisjointSet) RootOf(i int) int
RootOf returns root of the set with i-th element.
func (DisjointSet) SizeOf ¶
func (d DisjointSet) SizeOf(i int) int
SizeOf returns size of the set with i-th element.
Source Files
Valid 
Redistributable license