Transform

Bases: Generic[T]

              flowchart TD
              matchlab.core.dsu.DisjointSet[DisjointSet]

              

              click matchlab.core.dsu.DisjointSet href "" "matchlab.core.dsu.DisjointSet"
            

Disjoint set forest with "path compression" and "union by rank" heuristics.

This follows implementation from Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022

Initialise the disjoint set.

Methods:

• add –

  Add a new element to the disjoint set.

• union –

  Merge the sets containing elements x and y.

• get_components –

  Return the connected components of the disjoint set.

Attributes:

• parent (dict[T, T]) –
• rank (dict[T, int]) –

parent: dict[T, T] = {}

rank: dict[T, int] = {}

add(x: T) -> None

union(x: T, y: T) -> None

get_components() -> list[set[T]]