disjointset

package
v0.0.0-...-e834411 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Dec 4, 2024 License: Apache-2.0 Imports: 3 Imported by: 0

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

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL