What is union-find and where is it used?

Question

Accepted Answer

**Union-Find** (Disjoint Set Union) tracks a partition of elements into **disjoint sets** and supports two near-O(1) operations: **find** (which set is x in?) and **union** (merge two sets). It excels at **connectivity** queries.

## The idea

Each set is a tree with a representative root. With **path compression** and **union by rank/size**, operations run in nearly constant **amortized** time (inverse Ackermann, α(n)).

## Example

```python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # compress
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False               # already connected
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra           # attach smaller under larger
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True
```

## Complexity

- **find / union:** O(α(n)) ≈ O(1) amortized. **Space:** O(n).

## Applications

- **Kruskal's MST** — cycle detection while adding edges.
- **Connected components** / dynamic connectivity.
- **Cycle detection** in undirected graphs.
- **Percolation**, image segmentation, account/network merging.

## Pitfalls

Without path compression and union by rank, trees degrade to O(n) chains. It does not support efficient *splitting* of sets.

## Why it matters

Union-find answers "are these two things connected?" at massive scale with almost no cost.

It is the engine inside Kruskal's MST and many graph and clustering algorithms.

Its two optimizations are a memorable lesson in how small structural tricks yield near-constant-time performance.