The union-find algorithm maintains a changing collection of non-overlapping sets. Its core operations are make-set, which creates a singleton set; find, which returns a set’s representative; and union, which merges two sets. It supports connectivity tests without storing every member relationship explicitly.

The same technique, called disjoint set union, represents each set with a parent forest. The implementation below starts with that forest, then adds path compression and union by rank so repeated operations stay near-constant in amortized time.

How does the union-find algorithm represent sets?

A set is a component: a group of elements connected through previous union operations. Each element is a node with one parent pointer. A root points to itself, so parent[x] = x identifies the root. That root is the component’s representative.

make-set(x) creates a new component containing only x. It sets parent[x] = x and initializes a rank or size value. Initially, every item is its own representative. When two components merge, one root becomes a child of the other root. The resulting parent forest encodes membership: following parent links eventually reaches the representative.

To test whether two elements belong to the same component, compare their representatives. If find(a) = find(b), they are connected according to the unions performed so far. This structure tracks connectivity efficiently; it is not intended to enumerate the full route between two vertices.

How do you implement a union-find data structure with make-set, find, and union?

Store parent and rank in arrays or maps. The following pseudocode includes both standard optimizations:

make-set(x): Set parent[x] = x and rank[x] = 0.

find(x): If parent[x] is not x, replace parent[x] with find(parent[x]). Return parent[x].

union(a, b): Compute rootA = find(a) and rootB = find(b). If the roots match, stop. Otherwise, attach the lower-rank root below the higher-rank root. If the ranks match, choose either root as the parent and increase its rank by one.

For elements A through E, initialization produces:

• Initial: parent = {A:A, B:B, C:C, D:D, E:E}; rank = {A:0, B:0, C:0, D:0, E:0}.
• union(A, B): attach B to A; parent[B] = A and rank[A] = 1.
• union(C, D): attach D to C; parent[D] = C and rank[C] = 1.
• union(A, C): both roots have rank 1, so attach C to A and raise rank[A] = 2. D still points to C.
• union(D, E): finding D reaches A through C, then compresses D to point directly to A. E attaches to A.

The final parent array is {A:A, B:A, C:A, D:A, E:A}, with A as representative and rank A equal to 2. Calling find(D) now returns A immediately.

How do path compression and union by rank work?

Path compression changes every node visited by find to point directly to the root. In the example, D initially points to C, and C points to A. After find(D), D points to A. The operation may traverse several links once, but later searches from D skip those intermediate nodes.

Union by rank controls how roots are linked. Rank estimates a tree’s height: attach the smaller-rank tree beneath the larger-rank tree, and increase rank only when equal ranks merge. This avoids creating long chains. A size array can replace rank by attaching the smaller component to the larger one.

How does disjoint set union achieve near-constant amortized time?

Without either optimization, repeated unions can form a chain, making find take O(n) time. Union by rank limits tree height to O(log n), while path compression flattens the portions of trees that searches actually visit. Used together, a sequence of m operations on n elements takes O(m α(n)) amortized time, where α is the inverse Ackermann function and grows so slowly that it is effectively constant for practical input sizes. Each make-set is O(1), and the arrays require O(n) space.