Disjoint-Set Union

Disjoint-set union (DSU), also called union–find, answers one narrow question extremely well: after repeatedly joining groups, are two elements now in the same group? It represents a partition rather than the groups' contents, so it avoids moving every member when two large groups merge. The winning implementation stores one parent pointer per element and changes the forest opportunistically as queries arrive.

DSU is the right tool when connectivity grows monotonically. It is not a general set container and it cannot normally split a component after an edge or relation is removed.

The abstract contract is a partition #

Let $U$ be a finite universe. A partition $\mathcal{P}$ is a family of nonempty subsets of $U$ such that every element belongs to exactly one subset:

$$\bigcup_{S\in\mathcal{P}} S=U, \qquad S_i\cap S_j=\varnothing\quad\text{for }i\ne j.$$

The core operations are:

make_set(x)

Add a previously absent element as the singleton set {x}.

find(x)

Return a representative identifying the unique set that contains x.

union(a,b)

Replace the sets containing a and b

same_set(a,b) is simply find(a) == find(b). A useful implementation also tracks the number of components and, at each root, the component size.

The semantic invariant is an equivalence relation. At every point, same_set is reflexive, symmetric, and transitive, and union only coarsens the partition: two sets become one, but one set never becomes two.

A forest encodes the partition #

Assign every element an integer slot. parent[x] is another slot, and a root points to itself. Following parents from any element must terminate at exactly one root; that root is the set's current representative.

The representation invariants are:

1. parent[x] names an element in the same component as x.
2. Parent pointers form rooted trees—there are no directed cycles except a root's self-loop.
3. parent[r] == r exactly when r is a root.
4. Size or rank metadata is authoritative only at roots.
5. Two elements are in the same abstract set exactly when their parent chains end at the same root.

make_set(x) establishes all of these with parent[x] = x and size[x] = 1. A successful union finds two roots and changes exactly one root's parent. Attaching a root beneath a node inside the other tree would risk a cycle; attaching any non-root would fail to merge the whole component.

Without a balancing rule, a hostile sequence can create

7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0

and a find(7) takes linear time. The two classical heuristics attack different parts of that chain.

The two heuristics #

Union by size or rank prevents tall trees #

Union by size attaches the smaller root beneath the larger root. Whenever an element's depth increases by one, the size of the tree containing it at least doubles. No element can suffer more than $\lfloor\log_2 n\rfloor$ such doublings, so the tree height is $O(\log n)$ even without path compression.

Union by rank stores an upper-bound-like height certificate. Attach the lower-rank root beneath the higher-rank root; when the ranks tie, choose either root and increment the winner's rank. A rank-$r$ root represents at least $2^r$ elements, hence rank is at most $\lfloor\log_2 n\rfloor$.

After path compression, rank is no longer the actual height. It must not be recomputed downward: the old rank remains the ordering certificate used by future unions.

Path compression makes later finds cheaper #

A full-compression find(x) first reaches the root, then rewires every pointer on that search path directly to the root. It does not change which elements are equivalent; it changes only the encoding of the same partition.

Two one-pass variants are common:

Boost's DSU exposes both full compression and path halving. Iterative halving avoids recursion depth and often gives a compact hot loop; full compression is easiest to reason about and makes the postcondition explicit.

A complete implementation #

This dense-ID implementation uses union by size and iterative full path compression:

class DisjointSetUnion:
    def __init__(self, n: int):
        if n < 0:
            raise ValueError("n must be non-negative")
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, x: int) -> int:
        if not 0 <= x < len(self.parent):
            raise IndexError("element is outside the DSU universe")
        root = x
        while self.parent[root] != root:
            root = self.parent[root]

        while self.parent[x] != x:
            next_x = self.parent[x]
            self.parent[x] = root
            x = next_x
        return root

    def union(self, a: int, b: int) -> bool:
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a == root_b:
            return False

        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a

        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]
        self.components -= 1
        return True

    def same_set(self, a: int, b: int) -> bool:
        return self.find(a) == self.find(b)

    def component_size(self, x: int) -> int:
        return self.size[self.find(x)]

The Boolean result from union is useful: it says whether the partition actually changed. In graph algorithms, False often means an edge joined two vertices already connected by earlier edges.

Worked trace: compression changes shape, not membership #

Start with eight singleton sets and perform:

union(0,1)  union(2,3)  union(4,5)  union(6,7)
union(0,2)  union(4,6)  union(0,4)

Ties are resolved in favor of the first root. Immediately after the unions:

The abstract partition is already one set. Now find(7) walks 7→6→4→0 and rewires the path:

No set merge occurred during either find. The optimization is legal precisely because every rewritten node still points to an ancestor in the same tree and ultimately to the same root.

Why the amortized bound is so small #

Union by size alone gives $O(\log n)$ per find. Compression alone makes repeatedly visited paths cheap, but balancing prevents expensive new shapes from being manufactured faster than compression removes them. Their combination is substantially stronger than either proof in isolation.

Tarjan's analysis bounds a sequence of intermixed finds and unions by an inverse-Ackermann factor. With the usual accounting, $m$ operations over $n$ elements take

$$O\bigl(m\,\alpha(m,n)\bigr),$$

often simplified to $O(m\alpha(n))$. The inverse Ackermann function $\alpha$ is unbounded in the mathematical limit but grows more slowly than iterated logarithms over all ordinary input sizes. The operational conclusion is “almost constant amortized time,” not literal $O(1)$.

Connectivity as a streaming decision #

Suppose undirected edges arrive one at a time. Make one set per vertex. For edge $\{u,v\}$:

1. compute ru = find(u) and rv = find(v);
2. if the roots match, $u$ and $v$ were already connected, so the edge closes a cycle relative to the processed forest;
3. otherwise, unite the roots, decreasing the component count by one.

This gives incremental connectivity: every accepted relation persists. It is the core state machine behind Kruskal's minimum spanning tree algorithm. Sort edges by nondecreasing weight; accept an edge exactly when its endpoints currently have different representatives. DSU supplies the cycle test, while the cut/exchange proof supplies optimality—DSU alone does not prove that a spanning tree is minimum.

The same pattern groups accounts linked by verified identifiers, merges equivalence classes during compilation, labels regions in an image, and tracks connected components as edges are added. In every case, the question is equivalence under monotone merges, not reachability through a graph that can lose edges.

Boundaries and variants #

Deletions require a different algorithm #

After edges a—b—c have been united, removing b—c may or may not split the component depending on other paths. The DSU forest does not store those paths, so it lacks enough information to decide. Use an offline ordering trick, a rollback structure, or a fully dynamic connectivity algorithm when deletions matter.

A rollback DSU records each changed parent/size field on a stack and undoes changes in reverse order. It normally keeps union by size but omits path compression: compression rewrites an unbounded number of fields per query and makes rollback bookkeeping expensive. Finds then cost $O(\log n)$, and each successful union/rollback changes $O(1)$ recorded fields.

Aggregate data belongs at roots #

Component size, sum, minimum label, or another mergeable aggregate can be stored at roots and combined during union. Queries must first find the current root. Per-member enumeration is different: DSU does not naturally maintain a compact iterable list of each component, and adding one changes update and memory costs.

Relative constraints need potentials #

Some problems ask not only whether $a$ and $b$ are related, but the difference between their labels—for example parity or coordinate offsets. A potential DSU stores an edge label from each node to its parent and accumulates labels during find. Compression must compose those labels as well as parent pointers. Updating only parent preserves connectivity while silently corrupting the relative-value invariant.

Concurrency is not automatic #

Even find writes when compression is enabled. Concurrent calls can race on parent and rank/size state unless the implementation proves an atomic algorithm or uses synchronization. Treat an ordinary DSU as mutable, single-owner state.

Failure diagnostics #

1. Does every parent chain reach a self-parent root, or can a union create a cycle?
2. Does union call find first and attach root to root?
3. Is size/rank read and updated only at roots?
4. Does a redundant union leave components and root metadata unchanged?
5. Is the representative being mistaken for a stable or ordered component name?
6. Are all element IDs valid and never reused for different objects?
7. Does the workload contain deletions or splits that ordinary DSU cannot represent?
8. If rollback is required, was path compression deliberately removed or fully logged?
9. If potentials are stored, does compression update both the parent and accumulated label?
10. Are concurrent finds/unions synchronized by a proven design?

Exercises #

1. Prove that union by size without compression limits tree height to $\lfloor\log_2 n\rfloor$.
2. Starting from ten singletons, choose unions that maximize the height under union by rank and draw the resulting ranks.
3. Modify the implementation so union returns the new root and explain why clients still must not persist it as a semantic ID.
4. Process edges (0,1), (2,3), (1,2), (0,3), (3,4) and identify which edge first closes a cycle.
5. Give two different underlying graphs that produce identical DSU state but respond differently when one processed edge is deleted. Explain why this proves that deletion cannot be implemented from DSU state alone.