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

                func (d DisjointSet) SizeOf(i int) int

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

                  Source Files