# Union-Find (Disjoint Set Union) — Path Compression, Union by Rank and Uses

Source: https://skills101.in/learn/dsa/dsa-union-find-disjoint-set — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-21.

On the first day of college, 600 students know nobody. Then friendships form: "Asha and Ravi are friends", "Ravi and Meena are friends". At any moment the principal may ask, "Are Asha and Meena in the same friend circle?" or "How many separate circles are there now?" Running BFS after every new friendship would be slow. **Union-Find**, also called **Disjoint Set Union (DSU)**, handles both questions in **nearly O(1)** each.

## 1. The idea: every group has a leader

Each group (set) is stored as a small tree. Every element points to a **parent**; the element at the top of the tree points to **itself** and is the group's **root** (leader). Two elements are in the same group exactly when they have the same root.

Only two operations are needed:

- **find(x)** — follow parent pointers up to the root and return it.
- **union(a, b)** — find both roots; if they differ, make one root the parent of the other. The two groups are now one.

At the start, every element is its own group: `parent[i] = i`.

![The parent array of six elements after union(0,1), union(2,3), union(1,3), union(4,5) and union(0,2); the last union changes nothing because 0 and 2 are already in the same set; final sets {0, 1, 2, 3} and {4, 5}](https://skills101.in/learn-img/dsa/dsu-unions.svg)

## 2. Two tricks that make it fast

Without care, the trees can become long chains, and `find` becomes O(n). Two small tricks fix this.

**Path compression.** During `find(x)`, after finding the root, point every node on the path **directly** at the root. The next `find` on any of them takes one step.

![Path compression: before, the parent pointers form a chain 4 to 3 to 2 to 1 to 0; after find(4), nodes 1, 2, 3 and 4 all point directly to the root 0](https://skills101.in/learn-img/dsa/path-compression.svg)

**Union by rank.** When joining two trees, attach the **shorter** tree under the root of the taller one, so the height does not grow. `rank` is an upper bound on the tree's height. (Union by **size** — attach the smaller group under the larger — works just as well and also tells you group sizes.)

With **both** tricks, a sequence of m operations takes O(m · α(n)), where α is the inverse Ackermann function. α(n) is at most 4 for any n you will ever meet, so in practice each operation is **constant time**.

```python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.groups = 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, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                      # already in the same group
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra                   # ra is the taller tree
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.groups -= 1
        return True

d = DSU(6)
for a, b in [(0, 1), (2, 3), (1, 3), (4, 5), (0, 2)]:
    print(f"union({a},{b}) ->", d.union(a, b), d.parent)
print("same(1, 2)?", d.find(1) == d.find(2), " same(3, 4)?", d.find(3) == d.find(4))
print("groups:", d.groups)
```

```text
union(0,1) -> True [0, 0, 2, 3, 4, 5]
union(2,3) -> True [0, 0, 2, 2, 4, 5]
union(1,3) -> True [0, 0, 0, 2, 4, 5]
union(4,5) -> True [0, 0, 0, 2, 4, 4]
union(0,2) -> False [0, 0, 0, 2, 4, 4]
same(1, 2)? True  same(3, 4)? False
groups: 2
```

Notice `parent[3]` is still 2, not 0. Path compression is **lazy**: it only flattens a path when someone calls `find` on it.

For very deep trees, a recursive `find` can hit Python's recursion limit. An iterative version first walks to the root, then walks the path again to re-point each node.

## 3. Union by size in Java

```java
public class Main {
    static int[] parent, size;

    static int find(int x) {
        int root = x;
        while (parent[root] != root) root = parent[root];
        while (parent[x] != root) {          // second pass: compress the path
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }

    static boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;                     // smaller group goes under the larger
        size[ra] += size[rb];
        return true;
    }

    public static void main(String[] args) {
        int n = 7;
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
        int[][] friends = {{0, 1}, {1, 2}, {3, 4}, {5, 6}, {4, 6}};
        for (int[] f : friends) union(f[0], f[1]);
        System.out.println("size of 0's circle = " + size[find(0)]);
        System.out.println("size of 3's circle = " + size[find(3)]);
        System.out.println("0 and 5 together? " + (find(0) == find(5)));
    }
}
```

```text
size of 0's circle = 3
size of 3's circle = 4
0 and 5 together? false
```

The iterative `find` cannot overflow the stack, which matters when n is around 10⁵ or more.

## 4. What Union-Find is used for

| Problem | How DSU helps |
|---|---|
| Number of connected components / friend circles | start with n groups; every successful union lowers the count by 1 |
| Detect a cycle in an **undirected** graph | an edge whose ends are already in the same group closes a cycle |
| Kruskal's minimum spanning tree | take an edge only if `union` returns True |
| Redundant connection | the first edge for which `union` returns False |
| Accounts merge, similar strings | union items that share an email or are "similar", then group by root |
| Number of islands **as land is added** | each new land cell unions with its land neighbours |

```python
def find(parent, x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]      # path halving, a simple compression
        x = parent[x]
    return x

def first_cycle_edge(n, edges):
    parent = list(range(n))
    for u, v in edges:
        ru, rv = find(parent, u), find(parent, v)
        if ru == rv:
            return (u, v)                  # u and v were already connected
        parent[ru] = rv
    return None

print(first_cycle_edge(4, [(0, 1), (1, 2), (2, 3), (3, 1)]))
print(first_cycle_edge(4, [(0, 1), (1, 2), (2, 3)]))
```

```text
(3, 1)
None
```

**Limits:** DSU only **merges**. It cannot split a group or remove an edge, and it does not find the actual **path** between two elements. It also does not detect cycles in **directed** graphs — use DFS colours or Kahn's algorithm for that.

## Common mistakes

- Comparing `parent[a] == parent[b]` instead of `find(a) == find(b)`. Two elements can share a root without sharing a direct parent.
- In `union`, linking `a` to `b` instead of **root** to **root**: `parent[find(a)] = find(b)`.
- Forgetting to initialise `parent[i] = i`.
- Using DSU for directed-graph cycles or for problems where connections are removed.
- Writing a recursive `find` without compression on large inputs, which is slow and can overflow the stack.

## Quick recap

- Each group is a tree; the root is the leader; `find` climbs to the root, `union` links two roots.
- Path compression flattens paths during `find`; union by rank or size keeps trees short.
- With both, each operation is effectively O(1) (O(α(n)) amortised).
- Uses: counting components, undirected cycle detection, Kruskal's MST, merging accounts.
- It can only merge, never split.


Practice quiz and free certificate: https://skills101.in/learn/dsa/dsa-union-find-disjoint-set