Union-Find (Disjoint Set)

Union-Find — also called a Disjoint Set Union, or DSU — is a data structure that keeps a collection of elements split into non-overlapping groups and answers two questions fast: are these two elements in the same group? and merge the groups these two belong to. It is the workhorse behind connectivity queries, cycle detection in graphs, and Kruskal's minimum-spanning-tree algorithm. You will build it as a factory: unionFind(n) creates a structure over the n elements 0..n-1, each starting in its own one-element set, and returns an object with find, union, connected, and count. See the disjoint-set data structure for background.

Signature

unionFind(n) // create a structure over elements 0..n-1, each in its own set
// returns:
//   find(x)         -> the representative (root) of x's set
//   union(x, y)     -> merge x's and y's sets; true if they were separate
//   connected(x, y) -> are x and y in the same set?
//   count()         -> how many disjoint sets remain right now

Examples

const uf = unionFind(5); // {0} {1} {2} {3} {4} — five singleton sets
uf.count(); // 5
uf.connected(0, 2); // false — different sets

uf.union(0, 1); // true  — joined {0} and {1} into {0,1}
uf.union(1, 2); // true  — now {0,1,2}
uf.connected(0, 2); // true  — 0 and 2 are transitively connected
uf.union(0, 2); // false — already in the same set
uf.count(); // 3     — {0,1,2} {3} {4}

Notes

• Elements are 0..n-1 — n integer-indexed elements, each starting in its own singleton set.
• find returns a representative — every set has one root element, and two elements are in the same set exactly when find returns the same root for both.
• union reports whether it merged — it returns true when the two elements were in different sets (now joined) and false when they were already together.
• count tracks the number of sets — it starts at n and drops by one on each successful union; a redundant union or a self-union leaves it unchanged.
• Near-constant time — with path compression and union by rank, union and find run in amortized O(α(n)); α is the inverse Ackermann function, which is at most 4 for any n you will ever use.