Union Find

What is this?

A village keeps a single list: for every person, the name of whoever they answer to. To find someone's chief you follow that chain upward. To merge two families you point one chief at the other. To ask "are these two related?" you compare chiefs.

That is the entire data structure. It answers connectivity questions in near-constant time, and its one limitation is equally simple: families merge, they never split.

💡 Fun fact: with both optimisations — path compression and union by rank — the amortised cost per operation is O(α(n)), where α is the inverse Ackermann function. It grows so slowly that for any n that fits in the observable universe, α(n) < 5. In practice union-find is constant time, and it is one of the few data structures whose analysis is dramatically harder than its implementation.

🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.

The one-line idea: keep every node pointing toward its group's representative, and maintain a count of groups that decreases only when a union actually joins two different ones. Most union-find problems are answered by watching that counter, not by inspecting the structure.

1. The implementation worth memorising

parent = list(range(n))
rank   = [0] * n
components = n

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]     # path halving — compresses as it walks
        x = parent[x]
    return x

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return False                       # already together — nothing merged
    if rank[ra] < rank[rb]:
        ra, rb = rb, ra
    parent[rb] = ra                        # attach the shallower tree
    if rank[ra] == rank[rb]:
        rank[ra] += 1
    global components
    components -= 1
    return True

Two details do most of the work. union returns whether a merge happened, which is what lets callers count components, detect redundant edges, or stop early. And path halving — repointing each node at its grandparent during the walk — gives nearly all the benefit of full path compression in a single loop with no recursion.

2. The counter is usually the answer

A remarkable number of problems reduce to watching components:

The Earliest Moment When Everyone Become Friends is the first row: sort the friendship log by time, union each pair in order, and return the timestamp at which the counter hits one. Anything after that moment is irrelevant.

3. The limitation

Union-find cannot undo a merge. If a problem removes edges over time, the standard trick is to process the whole timeline backwards, turning removals into additions. If a problem needs true dynamic connectivity in both directions, union-find is the wrong structure and you should say so.

4. A 30-second worked example

Six people, friendships arriving in time order:

components = 6
t=1  (0,1) merge → 5
t=3  (2,3) merge → 4
t=4  (1,2) merge → 3      {0,1,2,3} now one group
t=7  (0,3) same root → no change, still 3     ← redundant edge
t=9  (4,5) merge → 2
t=12 (3,5) merge → 1      everyone connected → answer 12

Note t=7: both endpoints already shared a root, so union returned False and the counter did not move. Recognising redundant edges for free is exactly why the return value matters.

5. Where you'll actually meet this

• Network reliability. "At what point does this network become fully connected?" over a log of link activations.
• Kruskal's algorithm. Minimum spanning trees sort edges by weight and union them, skipping any edge whose endpoints already share a root.
• Image segmentation. Merging adjacent pixel regions by similarity is union-find over a grid.
• Account and identity merging. Deduplicating users when new "these two are the same person" facts arrive is exactly this, and the never-un-merge limitation is a real operational problem.
• Compiler optimisation. Type unification and value-numbering both use disjoint sets.

6. Problems in this chapter

▶ The Earliest Moment When Everyone Become Friends

Given timestamped friendships, find when the whole group first becomes connected. Sort by time, union in order, and return the timestamp at which the component counter reaches one.
Pattern: union-find with a component counter. Target: O(m log m) for the sort, near-linear thereafter.

7. Common pitfalls 🚫

• Forgetting to sort by time. The log is not given in chronological order, and processing it as-is silently answers a different question.
• Not compressing paths. Without it, a degenerate chain makes find O(n) and the whole solution quadratic.
• Decrementing the counter unconditionally. Only decrement when the roots differed; otherwise redundant edges corrupt the count.
• Comparing parent[a] == parent[b]. Connectivity is about roots, so compare find(a) == find(b).
• Recursive find on large inputs. It can exceed the stack depth; the iterative loop above avoids it.
• Trying to un-merge. The structure cannot do it — process removals in reverse instead.
• Returning the wrong "never" case. If the counter never reaches one, the answer is -1, not the last timestamp.

8. Key takeaways

1. Everything points toward a representative. find walks up, union links two roots.
2. Both optimisations matter. Compression plus rank gives effectively constant time.
3. Make union report whether it merged — that boolean answers redundancy and drives the counter.
4. Watch the component counter. Most problems in this family are answered by it alone.
5. Merges are permanent. Reverse the timeline if edges are removed.
6. Compare roots, never parents.
7. Why interviewers like it: the structure is twenty lines, so the question is always whether you can recognise a connectivity problem in disguise and know what the counter is telling you.

Order: The Earliest Moment When Everyone Become Friends.