What is a disjoint-set (union-find) structure with path compression and union by rank?

Question

Accepted Answer

A **disjoint-set** (union-find) tracks elements partitioned into non-overlapping groups and answers "**are these two in the same group?**" and "**merge two groups**" in **near-constant time**. With **path compression** and **union by rank**, both operations run in **O(α(n))** — effectively O(1) (α is the inverse Ackermann function).

## How it works

Each set is a tree; the **root** is the set's representative. `find` walks to the root; `union` links one root under another.

```text
find(x): follow parents to the root
union(a,b): attach the shorter tree under the taller (by rank)
path compression: after find, point nodes DIRECTLY at the root
   before:  a->b->c->root      after:  a->root, b->root, c->root
```

## Code

```python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n
    def find(self, x):                       # path compression
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # halve path
            x = self.parent[x]
        return x
    def union(self, a, b):                   # union by rank
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        return True
```

| Operation | Time (with both optimizations) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Common uses

- **Kruskal's MST** — merge components without forming cycles.
- **Connected components** in a graph or grid.
- **Dynamic connectivity** and network/percolation problems.

## Why it matters

Union-find solves grouping and connectivity problems that would otherwise need repeated O(n) graph traversals, collapsing them to almost O(1) per query.

It is a go-to tool whenever you must incrementally merge sets and test connectivity — a frequent senior-level interview topic.