DisjointSet (yog-fsharp)

DisjointSet Module

Namespace: Yog
Assembly: Yog.FSharp.dll

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

Types

Type	Description
DisjointSet<'a>	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 (effectively constant for all practical purposes, less than 5 for 2^65536 elements).

Functions and values

Function or value Description


                
                  
                    
                      add element dsu

Full Usage: add element dsu

Parameters:

element : 'a

dsu : DisjointSet<'a>

Returns: 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.

Time Complexity: O(log n) without path compression (amortized O(α(n)) with find)

Example

1: 
2:

let dsu = empty |> add 1 |> add 2 |> add 3
// Three separate sets: {1}, {2}, {3}

val dsu: obj

element : 'a
dsu : DisjointSet<'a>

Returns: DisjointSet<'a>


                
                  
                    
                      connected x y dsu

Full Usage: connected x y dsu

Parameters:

x : 'a

y : 'a

dsu : DisjointSet<'a>

Returns: 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.

Time Complexity: O(α(n)) amortized

Example

1: 
2: 
3:

let dsu = fromPairs [(1, 2); (3, 4)]
let (dsu2, result1) = connected 1 2 dsu   // => true
let (dsu3, result2) = connected 1 3 dsu2  // => false

Use Cases

Cycle detection in undirected graphs
Dynamic connectivity checking
Network connectivity verification

val dsu: obj

val dsu2: obj

val result1: obj

val dsu3: obj

val result2: obj

x : 'a
y : 'a
dsu : DisjointSet<'a>

Returns: DisjointSet<'a> * bool


                
                  
                    
                      countSets dsu

Full Usage: countSets dsu

Parameters:

dsu : DisjointSet<'a>

Returns: int

Returns the number of disjoint sets.

Counts the distinct sets by finding the unique roots.

Time Complexity: O(n × α(n)) where n is the number of elements

Example

1: 
2:

let dsu = fromPairs [(1, 2); (3, 4)]
let count = countSets dsu  // => 2 (sets: {1,2} and {3,4})

Use Cases

Counting connected components in a graph
Verifying if all elements are connected (countSets = 1)

val dsu: obj

val count: obj

dsu : DisjointSet<'a>

Returns: int

Full Usage: empty

Returns: DisjointSet<'a>

Creates a new empty disjoint set structure.

Returns: DisjointSet<'a>


                
                  
                    
                      find element dsu

Full Usage: find element dsu

Parameters:

element : 'a

dsu : DisjointSet<'a>

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

Time Complexity: O(α(n)) amortized (inverse Ackermann)

Example

1: 
2: 
3:

let dsu = empty |> add 1 |> add 2 |> union 1 2
let (dsu2, root) = find 1 dsu
// root is the representative of the set containing 1 and 2

val dsu: obj

val dsu2: obj

val root: obj

element : 'a
dsu : DisjointSet<'a>

Returns: DisjointSet<'a> * 'a


                
                  
                    
                      fromPairs pairs

Full Usage: fromPairs pairs

Parameters:

pairs : ('a * 'a) seq

Returns: DisjointSet<'a>

Creates a disjoint set from a sequence 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.

Time Complexity: O(k × α(n)) where k is the number of pairs

Example

1: 
2:

let dsu = fromPairs [(1, 2); (3, 4); (2, 3)]
// Results in: {1,2,3,4} as one set

Use Cases

Building DSU from edge lists in graph algorithms
Quick setup for connected component problems
Union-Find based cycle detection

val dsu: obj

pairs : ('a * 'a) seq

Returns: DisjointSet<'a>

Full Usage: size dsu

Parameters:

dsu : DisjointSet<'a>

Returns: int

Returns the total number of elements in the structure.

Time Complexity: O(1)

Example

1: 
2:

let dsu = empty |> add 1 |> add 2 |> add 3
let n = size dsu // => 3

val dsu: obj

val n: obj

dsu : DisjointSet<'a>

Returns: int


                
                  
                    
                      toLists dsu

Full Usage: toLists dsu

Parameters:

dsu : DisjointSet<'a>

Returns: 'a list list

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.

Time Complexity: O(n × α(n))

Example

1: 
2:

let dsu = fromPairs [(1, 2); (3, 4); (5, 6)]
let sets = toLists dsu  // => [[1; 2]; [3; 4]; [5; 6]] (order may vary)

Use Cases

Extracting connected components for further processing
Grouping elements by their connectivity
Visualizing the partition structure

val dsu: obj

val sets: obj

dsu : DisjointSet<'a>

Returns: 'a list list


                
                  
                    
                      union x y dsu

Full Usage: union x y dsu

Parameters:

x : 'a

y : 'a

dsu : DisjointSet<'a>

Returns: 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.

Time Complexity: O(α(n)) amortized

Example

1: 
2: 
3:

let dsu = empty |> add 1 |> add 2 |> add 3
let dsu2 = union 1 2 dsu // {1,2}, {3}
let dsu3 = union 2 3 dsu2 // {1,2,3}

val dsu: obj

val dsu2: obj

val dsu3: obj

x : 'a
y : 'a
dsu : DisjointSet<'a>

Returns: DisjointSet<'a>