Skills101

AdvancedData Structures & Algorithms · Lesson 32 of 40 · Updated ·

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

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}

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

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.

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)
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

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)));
    }
}
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

ProblemHow DSU helps
Number of connected components / friend circlesstart with n groups; every successful union lowers the count by 1
Detect a cycle in an undirected graphan edge whose ends are already in the same group closes a cycle
Kruskal's minimum spanning treetake an edge only if union returns True
Redundant connectionthe first edge for which union returns False
Accounts merge, similar stringsunion items that share an email or are "similar", then group by root
Number of islands as land is addedeach new land cell unions with its land neighbours
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)]))
(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 what you learned

📝 Quiz: Union-Find (Disjoint Set Union)5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →