disjoint

Documentation

Index

• type Set
  • func New(n int) 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)

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 New

func New(n int) Set

New returns a new disjoint where each element x is in the set {x}.

func (*Set) Find

func (dsPtr *Set) Find(x int) int

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

func (dsPtr *Set) FindBuffered(x int, buf []int) int

FindBuffered returns the current representation which contains x but uses buf to store the seen numbers for flattening.

func (*Set) Roots

func (dsPtr *Set) Roots() []int

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

func (dsPtr *Set) Sets() [][]int

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

func (dsPtr *Set) SmallestRep() []int

SmallestRep returns a []int where the the ith entry contains the smallest member of the set containing i.

func (*Set) String

func (dsPtr *Set) String() string

String returns a human-readable string of ds.

func (*Set) Union

func (dsPtr *Set) Union(x, y int)

Union unions the sets containing x and y in ds. This implements union by rank.

func (*Set) UnionBuffered

func (dsPtr *Set) UnionBuffered(x, y int, buf []int)

UnionBuffered unions the sets containing x and y in ds using the buffer provided. This implements union by rank.