Skip to content

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 ​

SyntaxDescription
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 ​

MethodSignatureReturnsDescription
find(T) => TTRoot representative of the set containing x
union(T, T) => booleanbooleanMerge sets; returns true if a merge occurred
connected(T, T) => booleanbooleanWhether x and y belong to the same set
setCount() => TTNumber 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 ​

OperationTime Complexity
findAmortized O(α(n)), nearly constant
unionAmortized O(α(n)), nearly constant
connectedAmortized O(α(n)), nearly constant
setCountO(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));  // 0

union ​

tyrus
const uf = UnionFind<u32>(5);

print(uf.union(0, 1));  // true
print(uf.union(2, 3));  // true
print(uf.union(0, 1));  // false

connected ​

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));  // true

setCount ​

tyrus
const uf = UnionFind<u32>(5);

print(uf.setCount());  // 5

uf.union(0, 1);
uf.union(2, 3);

print(uf.setCount());  // 3