Disjoint Set Union (DSU): Union by Rank & Path Compression

A Disjoint Set Union (DSU) data structure maintains a collection S = {S_1, S_2, ..., S_k} of disjoint dynamic sets.

Each set is identified by a canonical representative (the root of a tree).

Core Operations:

1. Make-Set(x): Initializes {x}.

2. Find-Set(x): Returns the representative of the set containing x.

3. Union(x, y): Merges the sets containing x and y.

1. Union by Rank:

Each node stores a rank (an upper bound on its height).

When unioning two sets, make the root with smaller rank point to the root with larger rank. If both ranks are equal, pick either root and increment its rank by 1.

This guarantees that tree depth never exceeds O(log n).

2. Path Compression:

During Find-Set(x), update the parent pointer of every node visited along the path to point directly to the root.

Combined Complexity:

Combining Union by Rank with Path Compression yields an amortized time of O(alpha(n)) per operation, where alpha(n) is the extremely slow-growing Inverse Ackermann function.