disjointset

Documentation

Index

• type Set
  • func NewSet[T comparable](size int) *Set[T]
  • func (s *Set[T]) FindRoot(a T) int
  • func (s *Set[T]) FindVal(idx int) (T, bool)
  • func (s *Set[T]) InSameGroup(a, b T) bool
  • func (s *Set[T]) Union(a, b T)
• type SimpleIntSet
  • func NewIntSet(size int) *SimpleIntSet
  • func (m *SimpleIntSet) FindRoot(a int) int
  • func (m *SimpleIntSet) Union(a int, b int)

Types

type Set

type Set[T comparable] struct {
	// contains filtered or unexported fields
}

Set is the universal implementation of a disjoint set. It's designed for sparse cases or non-integer types. If you are dealing with continuous integers, you should use SimpleIntSet to avoid the cost of a hash map. We hash the original value to an integer index and then apply the core disjoint set algorithm. Time complexity: the union operation has an inverse Ackermann function time complexity, which is very close to O(1).

func NewSet

func NewSet[T comparable](size int) *Set[T]

NewSet creates a disjoint set.

func (*Set[T]) FindRoot

func (s *Set[T]) FindRoot(a T) int

FindRoot finds the root of the set that contains a.

func (*Set[T]) FindVal

func (s *Set[T]) FindVal(idx int) (T, bool)

FindVal finds the value of the set corresponding to the index.

func (*Set[T]) InSameGroup

func (s *Set[T]) InSameGroup(a, b T) bool

InSameGroup checks whether a and b are in the same group.

func (*Set[T]) Union

func (s *Set[T]) Union(a, b T)

Union joins two sets in the disjoint set.

type SimpleIntSet

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

SimpleIntSet is the int disjoint set. It's not designed for sparse case. You should use it when the elements are continuous. Time complexity: the union operation is inverse ackermann function, which is very close to O(1).

func NewIntSet

func NewIntSet(size int) *SimpleIntSet

NewIntSet returns a new int disjoint set.

func (*SimpleIntSet) FindRoot

func (m *SimpleIntSet) FindRoot(a int) int

FindRoot finds the representative element of the set that `a` belongs to.

func (*SimpleIntSet) Union

func (m *SimpleIntSet) Union(a int, b int)

Union unions two sets in int disjoint set.