union_find

Documentation

Index

• type DisjointSet
  • func NewDisjointSet(n int) *DisjointSet
  • func (this *DisjointSet) Find(x int) int
  • func (this *DisjointSet) Len() int
  • func (this *DisjointSet) Union(x, y int) bool

Types

type DisjointSet

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

func NewDisjointSet

func NewDisjointSet(n int) *DisjointSet

NewDisjointSet returns an object representing a unordered_set containing n element.

func (*DisjointSet) Find

func (this *DisjointSet) Find(x int) int

Find returns the root of the tree that contains x. Complexity - O(α(n)), where α is the inverse Ackermann function.

func (*DisjointSet) Len

func (this *DisjointSet) Len() int

Len returns the size of the disjoint unordered_set. Complexity - O(1).

func (*DisjointSet) Union

func (this *DisjointSet) Union(x, y int) bool

Union merges the sets represented by x node and the y node into a single unordered_set. Returns whether or not the nodes were disjoint before the union operation (i.e. if the operation had an effect). Complexity - O(α(n)), where α is the inverse Ackermann function.