Lesson 14 of 16 Graphs

Union Find (Disjoint Set Union) Explained

Union find (disjoint set union) with path compression and union by size: connected components, redundant connection, accounts merge, Python and Java.

45-55 min intermediate 0/16 lessons done
Course contents Lesson 14 of 16 · 0 done
On this page (9 sections)
  1. What you will learn
  2. Signals
  3. The data structure
  4. Python
  5. Java
  6. Union-find vs BFS/DFS
  7. Key takeaways
  8. Exercises
  9. Quiz

What you will learn

  • What union-find stores and the two operations it supports.
  • Path compression and union by size, and why together they’re nearly O(1).
  • Three classic problems, plus a randomised check against DFS.

Signals

  • “Are these two connected?”, “how many groups/components?”, “merge accounts/friends”.
  • Edges arrive one at a time and you need connectivity after each.
  • “Which edge creates a cycle?” in an undirected graph.
  • Kruskal’s minimum spanning tree.

The data structure

Each element points to a parent; a root points to itself and names its set.

  • find(x): follow parents to the root.
  • union(a, b): find both roots; if different, attach one root under the other.

Two optimisations make this fast:

  • Path compression: after finding the root, point every node on the path directly at it, so future finds are short.
  • Union by size (or rank): hang the smaller tree under the larger, so trees stay shallow.

With both, a sequence of m operations takes O(m·α(n)), where α is the inverse Ackermann function, below 5 for any realistic n. Treat it as constant.

Python

"""Union-find (disjoint set union) with path compression and union by size."""
import random


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

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:  # path compression: point every node on the path at the root
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False  # already connected: this edge would close a cycle
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra  # union by size: hang the smaller tree under the larger
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)


def count_components(n, edges):
    uf = UnionFind(n)
    for a, b in edges:
        uf.union(a, b)
    return uf.components


def redundant_connection(edges):
    uf = UnionFind(len(edges) + 1)
    for a, b in edges:
        if not uf.union(a, b):
            return [a, b]
    return None


def accounts_merge(accounts):
    uf, owner, email_id = UnionFind(sum(len(a) - 1 for a in accounts)), {}, {}
    for name, *emails in accounts:
        for e in emails:
            if e not in email_id:
                email_id[e] = len(email_id)
                owner[e] = name
            uf.union(email_id[emails[0]], email_id[e])
    groups = {}
    for e, i in email_id.items():
        groups.setdefault(uf.find(i), []).append(e)
    return sorted([owner[es[0]], *sorted(es)] for es in groups.values())


def components_by_dfs(n, edges):
    graph = [[] for _ in range(n)]
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    seen, count = set(), 0
    for s in range(n):
        if s not in seen:
            count += 1
            stack = [s]
            seen.add(s)
            while stack:
                for nxt in graph[stack.pop()]:
                    if nxt not in seen:
                        seen.add(nxt)
                        stack.append(nxt)
    return count


if __name__ == "__main__":
    print(count_components(5, [[0, 1], [1, 2], [3, 4]]))
    print(redundant_connection([[1, 2], [1, 3], [2, 3]]), redundant_connection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]))
    print(accounts_merge([["John", "j@x.com", "john@y.com"], ["John", "john@y.com", "jj@z.com"],
                          ["Mary", "mary@m.com"], ["John", "johnny@n.com"]]))
    random.seed(1)
    for _ in range(500):
        n = random.randint(1, 30)
        edges = [[random.randrange(n), random.randrange(n)] for _ in range(random.randint(0, 40))]
        assert count_components(n, edges) == components_by_dfs(n, edges)
    print("500 random graphs: union-find matches DFS")

Output:

2
[2, 3] [1, 4]
[['John', 'j@x.com', 'jj@z.com', 'john@y.com'], ['John', 'johnny@n.com'], ['Mary', 'mary@m.com']]
500 random graphs: union-find matches DFS
  • Count components: start with n components and subtract one per successful union.
  • Redundant connection: the first edge whose endpoints are already connected closes a cycle; union returns False for it.
  • Accounts merge: union every email in an account with the account’s first email, then group emails by root. Two “John” accounts sharing john@y.com merge; the third John stays separate because the name alone proves nothing.
  • The random test compares component counts against a plain DFS on 500 graphs, including self-loops and repeated edges.

Java

public class UnionFind {
    private final int[] parent;
    private final int[] size;
    private int components;

    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        components = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // path halving: skip a level on the way up
            x = parent[x];
        }
        return x;
    }

    public 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;
        size[ra] += size[rb];
        components--;
        return true;
    }

    public int components() { return components; }

    public static void main(String[] args) {
        UnionFind uf = new UnionFind(5);
        int[][] edges = {{0, 1}, {1, 2}, {3, 4}, {2, 0}};
        for (int[] e : edges) {
            if (!uf.union(e[0], e[1])) System.out.println("cycle at edge " + e[0] + "-" + e[1]);
        }
        System.out.println("components: " + uf.components());
    }
}

Output:

cycle at edge 2-0
components: 2

The Java version uses path halving (parent[x] = parent[parent[x]] while walking up), a one-pass variant of path compression with the same complexity.

Union-find vs BFS/DFS

SituationBetter choice
Static graph, one-off component countEither; DFS is simple
Edges arrive over time, connectivity queries in betweenUnion-find
Need actual paths or distancesBFS/DFS
Kruskal’s MST, cycle detection while adding edgesUnion-find
Deleting edgesNeither directly (offline tricks needed)

Practise: union-find problems and the wider graph traversal section.

Key takeaways

  • Union-find tracks a partition into sets with find and union.
  • Path compression plus union by size gives effectively O(1) amortised operations.
  • A failed union (same root) means the edge closes a cycle.
  • Prefer it when edges arrive incrementally and you only need connectivity.

Exercises

  1. Number of provinces from an adjacency matrix with union-find.
  2. Kruskal’s minimum spanning tree: sort edges by weight, union if not connected.
  3. Longest consecutive sequence (LeetCode 128) using union-find over values.

Quiz

  1. What does find return, and what does it mean if two elements return the same value?
  2. What do path compression and union by size each prevent?
  3. How does union-find detect a cycle in an undirected graph?
Show answers
  1. The root representative of the element’s set; the same root means the two elements are in the same set (connected).
  2. Path compression flattens long paths created earlier; union by size stops tall trees forming in the first place.
  3. When adding edge (a, b), if find(a) == find(b) they’re already connected, so the edge closes a cycle.

Finished this lesson?

Mark it complete to track your progress (saved in this browser).