Union-Find Basics

1Introduction

This lecture defines a partition into pairwise disjoint sets and explains the representation and complexity of Union-Find, which provides the find and union operations.

2Disjoint-set partitions and operations

A partition of a set $$U$$U is a family $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P$$\mathcal P of nonempty subsets whose distinct members are pairwise disjoint and whose union is $$U$$U. Union-Find, also called disjoint-set union, supports the following operations on such a partition.

• $$\mathrm{find}\left(x\right)$$\operatorname{find}(x) returns the representative assigned to the set containing $$x$$x. Elements in one set have the same representative, so $$\mathrm{find}\left(x\right)=\mathrm{find}\left(y\right)$$\operatorname{find}(x)=\operatorname{find}(y) if and only if $$x$$x and $$y$$y belong to the same set.
• $$\mathrm{union}(x,y)$$\operatorname{union}(x,y) merges the sets containing $$x$$x and $$y$$y. It leaves the partition unchanged if they are already the same set.

Initially, each element forms a singleton set. Union-Find supports merging sets; splitting a set and deleting an element are not standard operations.

Every argument to find or union must belong to $$U$$U. If $$U=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$U=\varnothing, the initial partition is the empty family and there is no valid call to find or union.

3Parent-forest representation

Represent each set by a rooted tree and store the collection as a forest of rooted trees. Every element $$x$$x has a parent $$\mathrm{parent}\left[x\right]$$\operatorname{parent}[x], and a root $$r$$r satisfies $$\mathrm{parent}\left[r\right]=r$$\operatorname{parent}[r]=r. The root is the representative of its set. Find follows parent references to a root. Union makes one of two roots a child of the other.

3.1Path compression

Path compression changes the parent of every vertex visited by find to the root. It preserves the partition and representative while reducing the number of parent references in later find operations.

3.2Union by rank

Store at each root a rank that is an upper bound on tree height. Union makes the root of smaller rank a child of the root of larger rank. If their ranks are equal, it chooses either root as the child and increments the other root's rank. After path compression, rank need not equal actual height, but it remains suitable for the union rule.

4Complexity and scope

Assume that accessing or updating one array entry takes $$O\left(1\right)$$O(1) time. Initializing $$n$$n singleton sets and then processing $$m$$m find and union operations with path compression and union by rank admits the standard simplified upper bound $$O\left(\right(n+m\left)\alpha \right(n\left)\right)$$O((n+m)\alpha(n)), where $$\alpha$$\alpha is the inverse Ackermann function. More precise notation defines its argument using both $$n$$n and $$m$$m. This is an amortized complexity bound over the whole sequence; it does not state that every operation has constant worst-case time. The structure uses $$O\left(n\right)$$O(n) space.

When an edge is added to an undirected graph, unioning its endpoints permits connectivity queries by comparing representatives returned by find. Union-Find does not reconstruct a connecting path or a shortest path, and it does not directly support edge deletion.