# Union-Find — Part 1: The Pattern

Union-find (disjoint set union, **DSU**) tracks which items belong to the same group while groups keep merging. It supports two operations: **find(x)** returns the representative ("root") of x's group, and **union(a, b)** merges two groups. With **path compression** and **union by size/rank**, both run in **α(n)** amortized time, effectively constant (α grows so slowly it's ≤ 4 for any input that fits in the universe).

![Each group is a tree; find follows parent pointers to the root](diagrams/01-dsu.svg)

## 1. When to Use It

- "are these two nodes connected?" asked repeatedly while edges are **added** over time
- count **connected components** / groups (provinces, islands with dynamic land, merging accounts)
- detect the **edge that creates a cycle** in an undirected graph (Redundant Connection, valid tree)
- **Kruskal's minimum spanning tree**: add cheapest edges that join different components
- equations/relations: "a == b", "a != b" consistency checks

DFS/BFS can also count components, but union-find shines when edges arrive **incrementally** and you need answers after each one.

## 2. Template

```typescript
class DSU {
  parent: number[];
  size: number[];
  components: number;
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
    this.components = n;
  }
  find(x: number): number {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }
  union(a: number, b: number): boolean {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    this.components--;
    return true;
  }
}

function dsuDemo(n: number, edges: number[][]): any[] {
  const d = new DSU(n);
  const merged = edges.map(([a, b]) => d.union(a, b));
  return [merged, d.components];
}
```

```python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            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.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                               # attach smaller under larger
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

def dsu_demo(n, edges):
    d = DSU(n)
    merged = [d.union(a, b) for a, b in edges]
    return [merged, d.components]
```

- **Path compression** (`parent[x] = parent[parent[x]]`, or full compression with recursion) flattens trees during finds.
- **Union by size** attaches the smaller tree under the larger, keeping trees shallow.
- `union` returning `False` means the endpoints were already connected: in an undirected graph, that edge closes a **cycle**.

## 3. Kruskal's Minimum Spanning Tree

Sort edges by weight; for each edge, `union` its endpoints if they're in different components and add its weight. Stop after `n − 1` edges. O(E log E) for the sort; union-find makes each cycle check near-constant.

## Under the Hood: Why α(n)

Without either optimization a sequence of unions can build a chain, making `find` O(n). Union by size alone guarantees trees of height O(log n) (a node's tree at least doubles in size every time its depth increases). Adding path compression gives the inverse-Ackermann bound proved by Tarjan: amortized **O(α(n))** per operation. In interviews, "near O(1) amortized, with path compression and union by rank" is the expected answer.

## Common Pitfalls

1. **Comparing `parent[a] == parent[b]`** instead of `find(a) == find(b)`.
2. **Forgetting path compression or union by size**, leading to O(n) chains.
3. **Using union-find on directed graphs** for cycle detection: it only handles undirected connectivity.
4. **Mapping non-integer items** (emails, coordinates): give each a numeric id or use a dict-based parent map.
5. **Off-by-one with 1-indexed nodes**: allocate `n + 1` slots.

## Quick Reference

```text
parent[i] = i; find: while parent[x] != x: parent[x] = parent[parent[x]]; x = parent[x]
union: ra, rb = find(a), find(b); if same → False (cycle); attach smaller under larger
components: start n, decrement per successful union
Kruskal: sort edges; add if union succeeds; stop at n-1 edges
α(n) ≈ O(1) amortized
```