Union-Find (Disjoint Set Union)

Union-Find, also called Disjoint Set Union (DSU), maintains a partition of elements into disjoint sets. It supports two operations:

• find(x): which representative identifies the set containing x?
• unite(x, y): merge the sets containing x and y.

DSU shines when connectivity changes over time by adding edges.

Parent trees

Each set is represented as a tree. Every node points to a parent, and the root points to itself.

If find(2) reaches root 0, then 2 belongs to the set represented by 0.

Naive implementation

A basic DSU stores a parent array. find walks up to the root. Without optimizations, a tree can become a long chain, making find O(n).

Path compression

Path compression rewires every node on a find path directly to the root. Future finds become much faster.

Union by rank or size

Union by rank attaches the shallower tree under the deeper tree. Union by size attaches the smaller set under the larger set. Both keep trees short.

With both path compression and union by rank or size, operations take near O(α(n)) amortized time, where α is the inverse Ackermann function. Tarjan's analysis showed this is practically constant for any realistic input size.

Production DSU class

Connected components with DSU

Start with n separate sets. Every successful union reduces the component count by one.

Cycle detection in an undirected graph

When processing an undirected edge (u, v), if u and v are already in the same set, adding the edge creates a cycle.

Kruskal's minimum spanning tree algorithm

A minimum spanning tree (MST) connects all vertices of an undirected weighted graph with minimum total weight and no cycles.

Kruskal(edges, n):
    sort edges by weight
    make DSU with n singleton sets
    total = 0
    for edge (u, v, w) in sorted order:
        if unite(u, v) succeeds:
            add w to total
    return total

Challenge: Number of connected components using DSU

Challenge: Kruskal's MST total weight

Check your understanding