What Is Disjoint-Set Union? Tracking Connected Components

Enrichment: disjoint-set union maintains groups under repeated merges. Path compression and union by size make connectivity checks effectively constant-time across a long sequence.

Enrichment: beyond the current exercises

A disjoint-set union structure, also called union-find, maintains a collection of non-overlapping groups. It answers two questions:

find(value): which group representative contains this value?
union(left, right): merge two groups if they are different.

This is useful when edges arrive over time and the repeated question is whether two vertices are already connected. A graph traversal can answer one connectivity question. Disjoint-set union preprocesses the growing groups so many later questions are cheap. The current exercises use BFS or DFS; this structure is an extension for repeated connectivity queries and is not required there.

A forest of parent links

Each set is represented by a rooted tree. Every index stores a parent index. A root is its own parent. Following parent links reaches the representative, and two values are connected exactly when their representatives match.

The central invariant is:

Every parent link stays inside one set, every chain reaches a root, and a root points to itself.

Initially every value is alone, so every index is its own root. Union finds the two roots and makes one root the child of the other. Linking arbitrary input vertices instead of roots can detach part of a tree or create a cycle.

Two optimisations keep the trees shallow:

Union by size attaches the smaller tree below the larger root.
Path compression changes every parent followed by find to point directly at the root.

The following implementation validates indexes, uses an iterative find to avoid call-stack growth, and reports whether union actually merged two components.

Theme

Terminal

Press Run to execute this example. Use console.log to print a value.

Expected output is true, true, true, false, false, and 3. The last union returns false because 0 and 2 already have the same representative. Five singleton components minus two successful merges leaves three components.

The arrays use dense integer ids from 0 through count - 1. Validation makes an invalid id a RangeError instead of allowing an undefined array lookup to corrupt a parent chain. find is intentionally iterative: the first loop discovers the root, and the second loop compresses the path. The nullish fallbacks keep every indexed read typed, although a valid structure always has an entry at each validated index.

Trace the parent links

Start with parents [0, 1, 2, 3, 4]. After union(0, 1), root 1 points to root 0. After union(1, 2), finding 1 reaches 0, and root 2 also points to 0. Values 0, 1, and 2 now share representative 0.

Calling find(2) follows 2 to 0. On a taller tree, path compression rewrites every link on the route. It never changes set membership; it only gives future finds a shorter path.

Representatives are implementation details. After unions, the representative might be 0 or another value depending on tie choices. Client code should compare representatives, not require a particular one.

The component-count invariant is exact: it starts at the number of singleton sets and decreases once, and only once, for every successful merge. A repeated union, a self-union such as union(3, 3), and a connectivity query leave the count unchanged. A zero-element structure is valid and reports zero components, but every find call is out of range.

Cost

Without balancing, unions can form a chain and find can take O(n). Union by size alone keeps height O(log n). Union by size together with path compression has amortized O(α(n)) time per operation, where α is the inverse Ackermann function. It grows so slowly that it is below 5 for all practical input sizes, but it is not formally O(1).

Version	Find cost	Space
Arbitrary parent links	O(n) worst case	O(n)
Union by size only	O(log n) worst case	O(n)
Size plus path compression	O(α(n)) amortized	O(n)

“Amortized” describes the total cost across a sequence. One find may follow several links, but its compression makes later operations cheaper.

Where it fits

Disjoint-set union is ideal for incremental undirected connectivity, cycle detection while adding edges, and Kruskal's minimum-spanning-tree algorithm. Before adding an undirected edge u–v, compare their roots. Equal roots mean the edge closes a cycle. Different roots mean the edge joins two components, so union them.

It does not store a route between vertices, support directed reachability, or efficiently undo deleted edges. Use breadth-first or depth-first search when you need the actual path or all vertices in one traversal.

Common mistakes

Do not attach one arbitrary vertex to another. Find both roots first, then link one root to the other.

Do not update a size on a node that stopped being a root. Only the surviving root's size describes the whole component.

Do not decrement the component count when union returns false. No groups were merged.

Do not describe path compression as changing connectivity. It changes the shape of parent links while preserving every group.

Exercises

Process edges 0–1, 2–3, 1–2, and 0–3. State which edge first closes a cycle.
Add a componentSize(value) method that returns the size stored at the value's root.
Remove path compression and construct a sequence that demonstrates why union by size still limits tree height.
Compare answering 10,000 connectivity queries with repeated graph searches and with one disjoint-set structure.