UnionFind
UnionFind<T> implements a disjoint set (union-find) data structure with path compression and union by rank. It maintains a collection of non-overlapping sets and supports efficient union and find operations.
Construction
| Syntax | Description |
|---|---|
UnionFind<u32>(n) | Create a new disjoint set with n elements indexed from 0 to n - 1 |
UnionFind<u8>(n) | Same, with u8 element type |
UnionFind<u16>(n) | Same, with u16 element type |
UnionFind<u64>(n) | Same, with u64 element type |
Only unsigned integer types are allowed as the element type.
Methods
| Method | Signature | Returns | Description |
|---|---|---|---|
find | (T) => T | T | Root representative of the set containing x |
union | (T, T) => boolean | boolean | Merge sets; returns true if a merge occurred |
connected | (T, T) => boolean | boolean | Whether x and y belong to the same set |
setCount | () => T | T | Number of disjoint sets |
Elements are zero-indexed integers from 0 to n - 1. The native handle is released automatically when the binding goes out of scope.
Complexity
| Operation | Time Complexity |
|---|---|
find | Amortized O(α(n)), nearly constant |
union | Amortized O(α(n)), nearly constant |
connected | Amortized O(α(n)), nearly constant |
setCount | O(1) |
Where α is the inverse Ackermann function, which is effectively constant for all practical inputs.
Examples
Construction
tyrus
import { UnionFind } from "tyrus:algorithm";
const uf = UnionFind<u32>(10);find
tyrus
const uf = UnionFind<u32>(5);
print(uf.find(0)); // 0
print(uf.find(3)); // 3
uf.union(0, 1);
uf.union(1, 2);
print(uf.find(2)); // 0union
tyrus
const uf = UnionFind<u32>(5);
print(uf.union(0, 1)); // true
print(uf.union(2, 3)); // true
print(uf.union(0, 1)); // falseconnected
tyrus
const uf = UnionFind<u32>(5);
uf.union(0, 1);
uf.union(2, 3);
print(uf.connected(0, 1)); // true
print(uf.connected(0, 3)); // false
print(uf.connected(2, 3)); // truesetCount
tyrus
const uf = UnionFind<u32>(5);
print(uf.setCount()); // 5
uf.union(0, 1);
uf.union(2, 3);
print(uf.setCount()); // 3