yog - v2.0.0

yog/disjoint_set

Types

DisjointSet

</>

Disjoint Set Union (Union-Find) data structure.

Efficiently tracks a partition of elements into disjoint sets. Uses path compression and union by rank for near-constant time operations.

Time Complexity: O(α(n)) amortized per operation, where α is the inverse Ackermann function

pub type DisjointSet(a) {
  DisjointSet(parents: dict.Dict(a, a), ranks: dict.Dict(a, Int))
}

Constructors

Values

add

</> 
pub fn add(
  disjoint_set: DisjointSet(a),
  element: a,
) -> DisjointSet(a)

Adds a new element to the disjoint set.

The element starts in its own singleton set. If the element already exists, the structure is returned unchanged.

connected

</> 
pub fn connected(
  dsu: DisjointSet(a),
  x: a,
  y: a,
) -> #(DisjointSet(a), Bool)

Checks if two elements are in the same set (connected).

Returns the updated disjoint set (due to path compression) and a boolean result.

Example

let dsu = from_pairs([#(1, 2), #(3, 4)])
let #(dsu2, result) = connected(dsu, 1, 2)  // => True
let #(dsu3, result) = connected(dsu2, 1, 3) // => False

count_sets

</> 
pub fn count_sets(dsu: DisjointSet(a)) -> Int

Returns the number of disjoint sets.

Counts the distinct sets by finding the unique roots.

Example

let dsu = from_pairs([#(1, 2), #(3, 4)])
count_sets(dsu)  // => 2 (sets: {1,2} and {3,4})

find

</> 
pub fn find(
  disjoint_set: DisjointSet(a),
  element: a,
) -> #(DisjointSet(a), a)

Finds the representative (root) of the set containing the element.

Uses path compression to flatten the tree structure for future queries. If the element doesn’t exist, it’s automatically added first.

Returns a tuple of #(updated_disjoint_set, root).

from_pairs

</> 
pub fn from_pairs(pairs: List(#(a, a))) -> DisjointSet(a)

Creates a disjoint set from a list of pairs to union.

This is a convenience function for building a disjoint set from edge lists or connection pairs. Perfect for graph problems, AoC, and competitive programming.

Example

let dsu = disjoint_set.from_pairs([#(1, 2), #(3, 4), #(2, 3)])
// Results in: {1,2,3,4} as one set

new

</> 
pub fn new() -> DisjointSet(a)

Creates a new empty disjoint set structure.

size

</> 
pub fn size(dsu: DisjointSet(a)) -> Int

Returns the total number of elements in the structure.

to_lists

</> 
pub fn to_lists(dsu: DisjointSet(a)) -> List(List(a))

Returns all disjoint sets as a list of lists.

Each inner list contains all members of one set. The order of sets and elements within sets is unspecified.

Note: This operation doesn’t perform path compression, so the structure is not modified.

Example

let dsu = from_pairs([#(1, 2), #(3, 4), #(5, 6)])
to_lists(dsu)  // => [[1, 2], [3, 4], [5, 6]] (order may vary)

union

</> 
pub fn union(
  disjoint_set: DisjointSet(a),
  x: a,
  y: a,
) -> DisjointSet(a)

Merges the sets containing the two elements.

Uses union by rank to keep the tree balanced. If the elements are already in the same set, returns unchanged.

✨ Search Document