A disjoint-set union structure maintains a collection of non-overlapping sets while supporting two main operations:

• find(x): identify which set contains $x$;
• union(a,b): merge the sets containing $a$ and $b$.

A common representation stores each set as a rooted tree whose root acts as its representative.

Two optimizations make repeated operations very fast:

• union by rank or size attaches the smaller tree below the larger;
• path compression rewrites parent links during find so later searches become shorter.

Across a long sequence of operations, the amortized cost per operation is extremely close to constant, conventionally expressed using the inverse Ackermann function.

Disjoint-set union is useful when connectivity changes only by merging components, especially in minimum-spanning-tree algorithms.