Yog.DisjointSet (YogEx v0.70.0)

Disjoint Set Union (Union-Find) data structure for efficient set operations.

The disjoint-set data structure maintains a partition of elements into disjoint (non-overlapping) sets. It provides near-constant time operations to add elements, find which set an element belongs to, and merge two sets together.

Key Operations

Operation	Function	Complexity
Make Set	`add/2`	O(1)
Find	`find/2`	O(α(n)) amortized
Union	`union/3`	O(α(n)) amortized

Where α(n) is the inverse Ackermann function, which grows so slowly that it is effectively a small constant (≤ 4) for all practical inputs.

Optimizations

This implementation uses two key optimizations:

Path Compression: Flattens the tree structure during find operations, making future queries faster
Union by Rank: Attaches the shorter tree under the taller tree to minimize tree height

Use Cases

Kruskal's MST algorithm - detecting cycles
Connected components in dynamic graphs
Equivalence relations and partitioning
Percolation theory and network reliability

References

Migration Note: This module was ported from Gleam to pure Elixir in v0.53.0. The API remains unchanged.

Summary

Types

t()

Disjoint Set Union (Union-Find) data structure.

Functions

add(arg, element)

Adds a new element to the disjoint set.

connected?(dsu, x, y)

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

count_sets(dsu)

Returns the number of disjoint sets.

find(dsu, element)

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

from_pairs(pairs)

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

new()

Creates a new empty disjoint set structure.

size(arg)

Returns the total number of elements in the structure.

to_lists(dsu)

Returns all disjoint sets as a list of lists.

union(dsu, x, y)

Merges the sets containing the two elements.

Types

t()

@type t() :: {:disjoint_set, map(), map()}

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

Functions

add(arg, element)

@spec add(t(), term()) :: t()

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.

Example

iex> dsu =
...>   Yog.DisjointSet.new()
...>   |> Yog.DisjointSet.add(1)
...>   |> Yog.DisjointSet.add(2)
iex> Yog.DisjointSet.size(dsu)
2

connected?(dsu, x, y)

@spec connected?(t(), term(), term()) :: {t(), boolean()}

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

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

Example

iex> dsu = Yog.DisjointSet.from_pairs([{1, 2}, {3, 4}])
iex> {_dsu2, result1} = Yog.DisjointSet.connected?(dsu, 1, 2)
iex> result1
true
iex> {_dsu3, result2} = Yog.DisjointSet.connected?(dsu, 1, 3)
iex> result2
false

count_sets(dsu)

@spec count_sets(t()) :: non_neg_integer()

Returns the number of disjoint sets.

Counts the distinct sets by finding the unique roots.

Example

iex> dsu = Yog.DisjointSet.from_pairs([{1, 2}, {3, 4}])
iex> # 2 sets: {1,2} and {3,4}
iex> Yog.DisjointSet.count_sets(dsu)
2

find(dsu, element)

@spec find(t(), term()) :: {t(), term()}

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

Example

iex> dsu =
...>   Yog.DisjointSet.new()
...>   |> Yog.DisjointSet.add(1)
...>   |> Yog.DisjointSet.add(2)
...>   |> Yog.DisjointSet.union(1, 2)
iex> {_, root} = Yog.DisjointSet.find(dsu, 1)
iex> # Root is the representative of the set containing 1
iex> is_integer(root)
true

from_pairs(pairs)

@spec from_pairs([{term(), term()}]) :: t()

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

iex> dsu = Yog.DisjointSet.from_pairs([{1, 2}, {3, 4}, {2, 3}])
iex> # Results in: {1,2,3,4} as one set
iex> {_, root1} = Yog.DisjointSet.find(dsu, 1)
iex> {_, root4} = Yog.DisjointSet.find(dsu, 4)
iex> root1 == root4
true

new()

@spec new() :: t()

Creates a new empty disjoint set structure.

Example

iex> dsu = Yog.DisjointSet.new()
iex> Yog.DisjointSet.size(dsu)
0

size(arg)

@spec size(t()) :: non_neg_integer()

Returns the total number of elements in the structure.

Example

iex> dsu =
...>   Yog.DisjointSet.new()
...>   |> Yog.DisjointSet.add(1)
...>   |> Yog.DisjointSet.add(2)
iex> Yog.DisjointSet.size(dsu)
2

to_lists(dsu)

@spec to_lists(t()) :: [[term()]]

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

iex> dsu = Yog.DisjointSet.from_pairs([{1, 2}, {3, 4}, {5, 6}])
iex> result = Yog.DisjointSet.to_lists(dsu)
iex> length(result)
3

union(dsu, x, y)

@spec union(t(), term(), term()) :: t()

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.

Example

iex> dsu =
...>   Yog.DisjointSet.new()
...>   |> Yog.DisjointSet.add(1)
...>   |> Yog.DisjointSet.add(2)
...>   |> Yog.DisjointSet.union(1, 2)
iex> {_, root1} = Yog.DisjointSet.find(dsu, 1)
iex> {_, root2} = Yog.DisjointSet.find(dsu, 2)
iex> # Both elements now have the same root
iex> root1 == root2
true