# Union-Find (Disjoint Set Union) — Data Structures in Python

Source: https://www.skillbyai.com/en/data-structures-python/a-unionfind

> Track connected groups with near-constant-time union and find.

## Merging groups efficiently

**Union-find**, also called **disjoint set union (DSU)**, maintains a collection of non-overlapping groups and supports two operations: **`find(x)`**, which returns a representative (root) of x's group, and **`union(a, b)`**, which merges the groups of a and b. Each element points to a parent, and roots point to themselves. Two optimisations make it extremely fast: **path compression** (during `find`, point visited nodes directly at the root) and **union by rank or size** (attach the smaller tree under the larger). Together they give an amortised cost per operation of **O(α(n))**, where α is the inverse Ackermann function, which is less than 5 for any practical n, so effectively constant. Union-find answers "are these two connected?" as edges arrive, without re-running a graph search. Applications include **Kruskal's minimum spanning tree**, detecting cycles in undirected graphs, grouping duplicate accounts or records that share an email or phone number, network connectivity, image segmentation and percolation simulations.

## Union-find forest

Each group is a tree; find follows parents to the root, and path compression flattens the path.

![Two small trees of circles with arrows pointing upwards to their roots; a dashed arrow shows one tree being attached under the other root.](assets/figures/data-structures-python/section-7-map.svg) — Figure 7.1 — Find, union and path compression.

## Merging customer accounts that share contact details

Union by size with path compression.

```python
class UnionFind:
    def __init__(self):
        self.parent: dict[str, str] = {}
        self.size: dict[str, int] = {}

    def find(self, x: str) -> str:
        if x not in self.parent:
            self.parent[x], self.size[x] = x, 1
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:               # path compression
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a: str, b: str) -> bool:
        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]
        return True

accounts = [
    ("acc1", ["asha@x.com", "+91-90000-00001"]),
    ("acc2", ["asha.work@x.com", "+91-90000-00001"]),   # shares a phone with acc1
    ("acc3", ["ravi@x.com"]),
    ("acc4", ["asha.work@x.com"]),                     # shares an email with acc2
]

uf = UnionFind()
for acc, contacts in accounts:
    for contact in contacts:
        uf.union(acc, contact)

groups: dict[str, list[str]] = {}
for acc, _ in accounts:
    groups.setdefault(uf.find(acc), []).append(acc)
print(list(groups.values()))      # [['acc1', 'acc2', 'acc4'], ['acc3']]
```

## Cycle detection for free

When adding an undirected edge (u, v), if `find(u) == find(v)` already, the edge would create a cycle. Kruskal's algorithm uses exactly this check to build a minimum spanning tree.

**Quiz:** Which two optimisations make union-find operations nearly constant time?

- [x] Path compression and union by rank or size
- [ ] Sorting and hashing
- [ ] Recursion and memoisation
- [ ] Binary search and heaps

*Answer:* Path compression and union by rank or size. Together they keep the trees extremely shallow.