# Union-Find / Disjoint Set — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/union-find

> A structure that tracks disjoint groups and answers 'same group?' and 'merge groups' in near O(1).

## Groups as trees

**Union-Find** (Disjoint Set Union) represents each group as a tree, where every node points to a `parent`, and the root is its own parent. `find(x)` walks up to the root to identify x's group; `union(x, y)` links one root under the other.

## Path compression + union by rank

Two optimizations make this near-constant time: **path compression** flattens the tree during `find`, and **union by rank** attaches the smaller tree under the bigger one.

```python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True
```

Output:

```
uf = UnionFind(5)
uf.union(0, 1)
uf.find(0) == uf.find(1)  # True
```

## Where it's used

Detecting cycles in an undirected graph, Kruskal's MST, counting connected components, and 'friend circles' style problems all lean on Union-Find.

## Quick check

Test your understanding of amortized complexity.

**Quiz:** With path compression and union by rank, find/union run in roughly:

- [ ] O(n)
- [ ] O(log n)
- [ ] O(n log n)
- [x] Nearly O(1) (inverse-Ackermann)

*Answer:* Nearly O(1) (inverse-Ackermann). The amortized complexity is O(α(n)), the inverse Ackermann function, which is effectively constant for any realistic n.