Union-find: how it works and when to reach for it

Graphs Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
boss = [0, 0, 1, 2, 3]

def find(x: int) -> int:
    root = x
    while boss[root] != root:
        root = boss[root]
    while boss[x] != root:
        boss[x], x = root, boss[x]
    return root

print(find(4), boss)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 0 [0, 0, 0, 0, 0]

Right: the root is 0, and every node on the path now points straight at it.

Path compression pays once to flatten the chain, so later finds on these nodes take one step.

Why not the others?
  • B 0 [0, 0, 1, 2, 3]. The second loop rewrites each parent on the path.
  • C 4 [0, 0, 0, 0, 0]. find returns the root, which is 0.

30-second answer

Union-find tracks which items are in the same group. Each item points to a parent; the root names the group. find follows parents to the root, and union points one root at the other. Path compression flattens the paths it walks, and union by size hangs the smaller tree under the larger one. Together they make each operation nearly O(1).

Practise saying it · 60 s. No recording, just a timer

Explain union-find.

Say your answer out loud, then check which of these points you covered:

  • Parents and roots
  • Path compression
  • Union by size; near O(1)

Deep dive

Use it when edges arrive over time and you ask 'are these connected?' or 'how many groups?'.

Kruskal's minimum spanning tree and loop detection in undirected graphs both use it.

It cannot split groups apart; deletions need other tools.

Common mistakes

  • Writing union as boss[a] = b without finding roots, which corrupts groups.
  • Using recursion in find on very long chains without compression.

Senior take & follow-ups

Write the six-line version from memory; it comes up often.

Follow-up questions

Think of your answer first, then open the hint.

  1. What is α(n)?

    Show hint

    The inverse Ackermann function; it is at most 4 for any input that fits in the universe.

  2. How would you track group sizes?

    Show hint

    Keep a size per root and add sizes on union.

What each operation costs: Breadth First Search · Depth First Search · Topological Sort · Dijkstra Algorithm

Try it in a free tool

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.