Documentation ¶
Index ¶
- type Set
- func (dsPtr *Set) Find(x int) int
- func (dsPtr *Set) FindBuffered(x int, buf []int) int
- func (dsPtr *Set) Roots() []int
- func (dsPtr *Set) Sets() [][]int
- func (dsPtr *Set) SmallestRep() []int
- func (dsPtr *Set) String() string
- func (dsPtr *Set) Union(x, y int)
- func (dsPtr *Set) UnionBuffered(x, y int, buf []int)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Set ¶
type Set []int
Set is a simple implementation of the disjoint set structure as in https://en.wikipedia.org/wiki/Disjoint-set_data_structure. This is a efficient way of storing disjoint subsets of {0,...,n-1} when the only operations are checking if two elements are in same subet and taking the union of subsets.
func (*Set) Find ¶
Find returns the current representation of the set which contains x. This only (maybe) changes when the set containing x is unioned with another set. This also flattens the tree.
func (*Set) FindBuffered ¶
FindBuffered returns the current representation which contains x but uses buf to store the seen numbers for flattening.
func (*Set) Roots ¶
Roots returns a []int which contains the roots of the trees which make up the disjoint set. In particular, it returns one element from each disjoint set.
func (*Set) Sets ¶
Sets returns the sets of ds. Each set is sorted from smallest to largest and the set of sets is ascending in the smallest element of the sets.
func (*Set) SmallestRep ¶
SmallestRep returns a []int where the the ith entry contains the smallest member of the set containing i.
func (*Set) UnionBuffered ¶
UnionBuffered unions the sets containing x and y in ds using the buffer provided. This implements union by rank.