Union-Find / Disjoint Set (C)
Topics: data structures, union-find, amortized analysis
Problem
Implement a disjoint-set structure over caller-provided arrays (no allocation).
It tracks a partition of 0..n-1 into groups and answers "are these two in the
same group?" while supporting fast merges.
typedef struct { int *parent; int *rank; int n; int sets; } UnionFind;
void uf_init(UnionFind *u, int *parent, int *rank, int n); // parent[], rank[] size n
int uf_find(UnionFind *u, int x); // representative of x's set
bool uf_union(UnionFind *u, int a, int b); // true if they were separate
bool uf_connected(UnionFind *u, int a, int b);
int uf_count(const UnionFind *u); // number of sets
Each element starts in its own set, so uf_count begins at n and drops by one on
every successful union.
Key concepts
- Sets are trees of parent pointers. Each element points at a parent; the root
(an element pointing at itself) is the set's representative. Two elements are
connected iff they share a root.
- Path compression. During
find, point nodes nearer the root as you walk up.
This flattens the tree so future finds are nearly O(1).
- Union by rank. When merging, hang the shorter tree under the taller one so
the result stays shallow. Together with path compression, operations run in
inverse-Ackermann (effectively constant) amortized time.
This is the backbone of Kruskal's MST, connected-components, and dynamic
connectivity.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/uf && /tmp/uf
Sign in to submit your solution.