TechPrep
Linked structures, trees and graphsReadLabPracticeCheck

Union-find (disjoint sets)

Track which items are connected under repeated merges, in nearly constant time per operation.

Number of Connected Components. Given n nodes labelled 0..n-1 and a list of undirected edges, return how many connected components there are.

Signals that point here

The idea

Each component is a tree; parent[x] points toward its root, and two nodes are connected exactly when they have the same root. Union points one root at the other.

Two optimisations make it fast: path compression (here the halving form, parent[x] = parent[parent[x]]) and union by rank or size. With both, a sequence of m operations costs O(m·α(n)), where α is the inverse Ackermann function: effectively constant. This version uses compression only, which is usually enough in an interview; say what rank would add.

BFS or DFS also count components in O(n + e). Prefer union-find when edges stream in or when you need repeated connectivity queries.

def count_components(n: int, edges: list[list[int]]) -> int:
    parent = list(range(n))

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path halving
            x = parent[x]
        return x

    components = n
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            components -= 1
    return components

Complexity

With path compression alone, amortised O(log n) per operation; with union by rank as well, O(α(n)). O(n) space.

Pitfalls interviewers watch for

Variants worth knowing

Test it like the interviewer will

Step through it: count_components(6, [[0, 1], [2, 3], [1, 2], [4, 5], [0, 3]])

Each step is recorded from an instrumented copy of the Python above, run when the site was built.

Practice

Written for this site to drill the lesson. Not reported interview questions.

  1. Return the edge that, when removed, turns a graph back into a tree.
  2. Merge user accounts that share any e-mail address.
  3. Count islands in a grid where land cells are added one at a time, reporting the count after each.

Check yourself

When do two nodes belong to the same component?

When find returns the same root for both.

What do path compression and union by rank give you together?

Amortised O(α(n)) per operation.

Saved in this browser.