Disjoint Set (Union-Find) Concept

A Disjoint Set Union (DSU), or Union-Find data structure, maintains a collection of non-overlapping (disjoint) sets of elements partitioned from a common universe.

It is designed to execute two primary operations at near-instantaneous speed:

1. find(x): Determine which set element x belongs to (returns the canonical representative or "root" of x's set).
2. union(x, y): Merge the set containing x with the set containing y.

Tree-Based Representation

Elements in the same set form a directed tree where every node points upward to its parent. The root of the tree is its own parent (parent[root] == root) and acts as the set's unique identifier.

Copy codeSet 1 (Root = 0):        Set 2 (Root = 4):
      ( 0 )                   ( 4 )
     /     \                    |
   ( 1 )  ( 2 )               ( 5 )
     |
   ( 3 )

The Two Critical Optimizations

A naive Union-Find can degenerate into a linear chain, causing find() to run in O(n) time. Two optimizations make it blindingly fast:

1. Union by Rank (or Size)

Always attach the shorter tree underneath the root of the taller tree to minimize overall tree depth:

Copy codefun union(x: Int, y: Int): Boolean {
    val rootX = find(x)
    val rootY = find(y)
    if (rootX == rootY) return false // Already in same set!

    // Attach smaller rank tree to larger rank tree
    if (rank[rootX] < rank[rootY]) {
        parent[rootX] = rootY
    } else if (rank[rootX] > rank[rootY]) {
        parent[rootY] = rootX
    } else {
        parent[rootY] = rootX
        rank[rootX]++
    }
    return true
}

2. Path Compression

During find(x), make every traversed node point directly to the root, flattening the tree structure:

Copy codefun find(x: Int): Int {
    if (parent[x] != x) {
        parent[x] = find(parent[x]) // Path compression flattening!
    }
    return parent[x]
}

Copy codeBefore Path Compression:        After find(3):
       ( 0 )                         ( 0 )
         |                          /  |  \
       ( 1 )                    ( 1 )( 2 )( 3 )
         |
       ( 2 )
         |
       ( 3 )

The Inverse Ackermann Complexity α(n)

When combining Union by Rank and Path Compression, the amortized time complexity per operation is:

O(α(n))

Where α(n) is the Inverse Ackermann function. For any conceivable number of elements in the physical universe (n < 10^{80} atoms in the universe), α(n) ≤ 4. In practice, Union-Find operations run in effective O(1) constant time!

Production Use Cases

1. Cycle Detection in Undirected Graphs: When processing edges, if find(u) == find(v), adding edge (u, v) creates a cycle.
2. Kruskal's Minimum Spanning Tree: Greedily merges edges with lowest weight without introducing cycles.
3. Connected Components: Counting dynamic connected clusters in social networks or image pixel segmentation.

Summary

• DSU tracks partitioned sets with find (detects representative) and union (merges sets).
• Optimized via Path Compression and Union by Rank to run in near-constant O(α(n)) ≈ O(1) time.
• Standard tool for Kruskal's MST, cycle detection, and cluster analysis.