Parent-Pointer Forests as the Representation of Disjoint Sets

A partition of a set into disjoint blocks is one of the few structures whose entire state fits in a single array of integers, one per element. There is no header, no allocation per block, no pointer chasing through separately allocated nodes. The array holds, for each element, the index of another element in the same block, and the block itself is implicit: it is the set of elements whose chain of parents terminates at the same place.

The economy is not an accident of implementation. It follows from what the operations are allowed to ask. Disjoint-set structures are asked exactly two questions — which block contains this element, and merge these two blocks — and neither question requires the members of a block to be enumerable, ordered, or even distinguishable from one another. A representation that cannot enumerate is therefore not lossy with respect to the contract. Every refinement of this representation, from union by rank to the inverse-Ackermann analysis, is a change to how the parent array is maintained, never to what it stores.

One integer per element, roots point at themselves

The array is called parent and holds n entries for n elements. Each entry is either the index of another element in the same block or a marker meaning “this element is the root of its block”. The common encoding uses the element’s own index as the root marker, so a root satisfies parent[x] == x. An alternative encoding stores a negative value at roots, with the magnitude carrying the block size; that variant appears in Union by Rank and the Cost of Keeping Trees Shallow.

Two invariants define the structure. First, following parent links from any element must terminate, which means the directed graph of parent edges is a forest of arborescences rooted at the self-parenting elements. Second, two elements are in the same block exactly when their chains end at the same root. The second invariant is a statement about reachability, and it is the reason find exists: the only way to name a block is to name its root, so every operation begins by resolving an element to its root.

#include <stddef.h>

/* parent[i] == i marks a root. Caller guarantees 0 <= x < n. */
static size_t find(const size_t *parent, size_t x) {
    while (parent[x] != x)
        x = parent[x];
    return x;
}

/* Returns 1 if the blocks were distinct and have been merged. */
static int unite(size_t *parent, size_t a, size_t b) {
    size_t ra = find(parent, a);
    size_t rb = find(parent, b);
    if (ra == rb)
        return 0;
    parent[rb] = ra;      /* arbitrary choice: attach b's root under a's root */
    return 1;
}

find is a loop, not a recursion, and that matters. A chain of length n is a legal forest under the invariants, so the worst-case depth is n - 1 and a recursive formulation consumes n stack frames. At n in the millions that overflows a default thread stack on the common platforms, where the main thread typically gets a few megabytes and spawned threads rather less.

The unite above makes an arbitrary choice between the two roots. That choice is the entire subject of the next two articles in this cluster, because it determines the shape of the forest and therefore the length of the chains that find must walk.

The cost of a chain, and how unions build one

With the arbitrary attachment rule, the depth of the forest depends on the order of the union calls. Consider elements 0 through n-1, initially each alone. The call unite(0, 1) makes 1 a child of 0. Then unite(0, 2) finds root 0 and root 2, and attaches 2 under 0, so the depth stays 1. The sequence of unions with a fixed first argument builds a star and each find costs two steps.

The adversarial order is different: unite(0, 1), then unite(1, 2), then unite(2, 3), and so on. After the first call, 1 is a child of 0. The second call resolves 1 to root 0 and attaches 2 under 0, so the chain is 2 → 0, still short. To build a long chain the unions must attach the root of the growing tree underneath a fresh singleton, which the arbitrary rule does whenever the first argument is the new element: unite(1, 0) makes 0 a child of 1; unite(2, 1) resolves 1 to itself (it is a root) and attaches it under 2, giving 0 → 1 → 2. Repeating that pattern yields a path of length n-1, and a find on the oldest element walks every link.

This is not a rare coincidence. Any caller that processes edges in an order correlated with element numbering, or that merges “the new item into the existing group” by passing the new item first, produces exactly this shape. A merge loop over a stream of records, each unioned with the previous record, builds the path in n-1 unions at a cost of O(n) per union once the path is long, for O(n²) total. On n = 10⁶ that is on the order of 10¹² link traversals, which is not a theoretical concern.

The bound is therefore: n-1 unions and m finds cost O(n + m·n) in the worst case, with a single unite walking a path of n-1 links in the adversarial order. The naive structure is correct and compact, but its worst case is linear per operation, which is why no serious use of disjoint sets stops here.

What the array cannot express

Three limitations are structural rather than incidental, and they explain why the parent array is usually wrapped rather than exposed.

Blocks cannot be enumerated. Nothing in the array links siblings, so producing the members of the block containing x requires scanning all n entries and calling find on each, at O(n) per enumeration regardless of block size. Applications that need to emit the contents of a component — the edges of a spanning tree, the rows of an equivalence class — maintain a separate member list per block and splice those lists on union. That is a second structure with its own invariants, and keeping it consistent is where the bugs live.

Nothing can be removed. There is no operation that splits a block, and no way to delete an element without leaving a dangling parent reference. A block can only grow. Structures that support deletion either rebuild, or record enough history to undo, which is a distinct mechanism.

The forest carries no aggregate. A union destroys the identity of one root. Any value associated with a block — a count, a sum, a maximum — must be maintained outside the parent array and merged at the moment the roots are joined, before the losing root’s identity is overwritten. Storing the size at the root, as a negative parent value, is the cheapest instance of this pattern and doubles as the balance heuristic.

A fourth limitation is about naming rather than structure. The array is indexed by dense integers 0..n-1, so a caller holding arbitrary keys must first map them to indices, and that map is a hash table or a sorted array with its own cost per operation. When the key space is dense and known in advance, as with pixels, array cells, or graph vertices, the mapping is the identity and the structure is as cheap as it looks.

Sentinel and boundary choices that bite

The root marker parent[x] == x consumes no storage, but it collides with any convention that uses 0 as “no parent”. A caller that initializes a fresh array with calloc and treats 0 as the null index produces a structure in which element 0 is a root and every other element is its child, which is a valid forest and completely wrong. Initialization must write parent[i] = i for every i.

A signed representation invites the negative-size trick and then punishes it: the value -n at a root cannot be stored in an unsigned type, and mixing the two conventions in one array makes find ambiguous about how to test for a root. Pick one and keep it in one place.

Finally, the structure is not thread-safe by construction, and the reason is subtle: find mutates nothing here, so concurrent finds are safe, but a concurrent unite rewrites a root’s parent while another thread may be walking through that same node. The usual answers are one structure per thread with a merge phase, or external locking.

The mechanisms that repair the linear worst case — attaching the smaller tree under the larger, and flattening chains during find — are the subject of Union by Rank and the Cost of Keeping Trees Shallow, and the resulting bound is derived in The Inverse Ackermann Bound and Why It Is Effectively Constant.