disjointset

Documentation

Overview

Package DisjointSet provides a disjoint-set data structure with fixed size.

Index

• type DisjointSet
  • func New(size int) DisjointSet
  • func (d DisjointSet) Count() int
  • func (d DisjointSet) Disjoint(i, j int) bool
  • func (d *DisjointSet) Merge(i, j int) bool
  • func (d DisjointSet) RootOf(i int) int
  • func (d DisjointSet) Sets() [][]int
  • func (d DisjointSet) SizeOf(i int) int
  • func (d DisjointSet) SortedSets() [][]int
  • func (d DisjointSet) String() string

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) Count

func (d DisjointSet) Count() int

Count returns number of disjoint sets.

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) Sets

func (d DisjointSet) Sets() [][]int

Sets returns disjoint sets in an unspecified unorder.

Elements in each set are sorted.

func (DisjointSet) SizeOf

func (d DisjointSet) SizeOf(i int) int

SizeOf returns size of the set with i-th element.

func (DisjointSet) SortedSets

func (d DisjointSet) SortedSets() [][]int

SortedSets returns disjoint sets ordered by size, largest first.

For determinism, when size is the same, set with smaller first element is first.

Elements in each set are sorted.

func (DisjointSet) String

func (d DisjointSet) String() string

String formats a disjoint set as a human-readable string.