Union-Find (Connected Components)

Start from brute force

The obvious approach labels components directly, often called quick-find: give every node a label comp[i] = i, and for each edge whose endpoints have different labels, scan all n nodes and relabel every node carrying the second label with the first. At the end, count the distinct labels. It is correct, because each label always names exactly one component, and it needs O(n) space. But every successful merge costs a full O(n) scan, so the whole run is O(n · E): at the limits of 10⁵ nodes and 10⁵ edges, that is up to 10¹⁰ label checks. Union-find makes a merge one pointer change instead.

The approach

Represent each component as a tree of parent pointers whose root names the component; the invariant is that two nodes are connected exactly when following parents from each reaches the same root. Merging two components is then a single pointer change, root under root, and an edge whose endpoints already share a root is redundant. Two rules keep the trees shallow. Union by rank hangs the lower-rank root under the higher, so a tree of rank r holds at least 2^r nodes and no path is longer than log2 n. Path halving repoints nodes closer to the root during every find.

In the reference, parent = list(range(n)) makes every node its own root and rank starts at 0. find(x) loops while parent[x] != x, setting parent[x] = parent[parent[x]] before stepping up, which points each visited node at its grandparent. union(a, b) returns early when the roots match, swaps them so ra has the higher rank, sets parent[rb] = ra, and adds 1 to rank[ra] only on a tie. The answer is len({find(i) for i in range(n)}).

Walk through an example

Trace the first example, count_components(5, [[0, 1], [1, 2], [3, 4]]).

Complexity

Optimal: O((n + E) · α(n)) time with union by rank and path halving, where α is the inverse Ackermann function, at most 4 for any input that fits in memory; O(n) space for parent and rank. Brute force (quick-find relabeling): O(n · E) time, O(n) space.

Edge cases to test

• No edges: count_components(4, []) → 4. Every node is its own root.
• A redundant edge: [[0, 1], [1, 2], [0, 2]] on 3 nodes → 1. The last edge finds the same root twice and union returns early.
• A self-loop: count_components(3, [[2, 2]]) → 3. Both finds return 2, so nothing changes.
• Duplicate edges: count_components(2, [[0, 1], [0, 1]]) → 1; only the first copy merges anything.
• Merges in an awkward order: [[0, 1], [2, 3], [4, 5], [1, 2], [3, 4]] on 6 nodes → 1. Later edges join existing trees, so union must link roots, not the endpoints themselves.
• A single node: count_components(1, []) → 1; and n = 0, below the stated limits, returns 0.

Common mistakes

• Skipping path compression or union-by-rank — trees degenerate into O(n) chains.
• Union-ing the elements directly instead of their roots.
• Comparing parents instead of roots to test connectivity.
• Counting components as n minus the number of edges: redundant edges, self-loops and duplicates do not merge anything, so only successful unions may be subtracted.

Follow-ups an interviewer asks next

Edges arrive one at a time. How do you report the count after each?

Keep a counter that starts at n and decrements whenever union actually links two different roots. Each edge then costs O(α(n)) and the answer is always available without the final scan over all nodes. This is the usual form of the problem in streaming settings, such as tracking how many islands exist as land cells are added one by one.

What if edges can also be deleted?

Union-find cannot split a set, because nothing records which edge joined two trees. If all the operations are known in advance, process them in reverse, so deletions become additions. Otherwise you need a fully dynamic connectivity structure, which exists but is far more complex; rebuilding from scratch after each deletion costs O(n + E) each time.

How would you find the edge that creates a cycle?

Process the edges in order: the first edge whose endpoints already share a root closes a cycle, because a path between them existed before the edge was added. That is LeetCode’s Redundant Connection, and it is exactly the check Kruskal’s algorithm makes when it skips an edge while building a minimum spanning tree in order of increasing weight.

How do you get the size of each component?

Use union by size instead of rank: keep size[root], attach the smaller tree under the larger, and add the smaller size into the new root. The largest component is then a running maximum updated on each union. Union by size gives the same logarithmic height bound as union by rank, so the complexity is unchanged.

Where this shows up

Union-Find powers Kruskal’s minimum spanning tree, dynamic connectivity, cycle detection, and region/segment merging in images. Any “are these two in the same group, and merge groups fast” problem reaches for it.

Reference solution

def count_components(n, edges):
    parent = list(range(n))         # each node starts as its own root
    rank = [0] * n

    def find(x):                    # root of x, with path compression
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # halve the path
            x = parent[x]
        return x

    def union(a, b):                # merge the two sets (union by rank)
        ra, rb = find(a), find(b)
        if ra == rb:
            return                  # already connected — redundant edge
        if rank[ra] < rank[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        if rank[ra] == rank[rb]:
            rank[ra] += 1

    for a, b in edges:
        union(a, b)
    return len({find(i) for i in range(n)})


print(count_components(5, [[0, 1], [1, 2], [3, 4]]))  # -> 2
print(count_components(4, []))                        # -> 4

function countComponents(n: number, edges: number[][]): number {
  const parent = Array.from({ length: n }, (_, i) => i); // own root
  const rank = new Array(n).fill(0);

  function find(x: number): number {          // root, with compression
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];          // halve the path
      x = parent[x];
    }
    return x;
  }
  function union(a: number, b: number): void { // union by rank
    let ra = find(a), rb = find(b);
    if (ra === rb) return;                      // redundant edge
    if (rank[ra] < rank[rb]) { const t = ra; ra = rb; rb = t; }
    parent[rb] = ra;
    if (rank[ra] === rank[rb]) rank[ra]++;
  }

  for (const [a, b] of edges) union(a, b);
  const roots = new Set<number>();
  for (let i = 0; i < n; i++) roots.add(find(i));
  return roots.size;
}

console.log(countComponents(5, [[0, 1], [1, 2], [3, 4]])); // -> 2
console.log(countComponents(4, []));                       // -> 4