Skip to content
Tutorials Center
My learning

Topics

Lesson 130 of 225 ยท Graphs

Union-Find (Disjoint Sets)

Learn union-find, also called disjoint set union: find with path compression, union by size, near constant time, counting components and redundant connections.

Suppose friendships appear one at a time: "Ana and Ben are now friends", "Ben and Cy are now friends". After each announcement you may be asked: "Are Ana and Cy in the same friend circle?" You could rerun a breadth-first search every time, but that costs O(V + E) per question. Union-find, also called a disjoint-set union (DSU), answers the same question in almost constant time, even while connections keep arriving.

A union-find structure keeps a collection of disjoint sets (no element is in two sets) and supports two operations:

  • find(x): which set is x in? It returns a representative (also called the root) of the set. Two elements are in the same set exactly when find gives the same answer.
  • union(a, b): merge the set of a and the set of b into one.

It is short enough to write from memory, and it powers Kruskal's minimum spanning tree algorithm, cycle checks in undirected graphs, and many "group the things that are connected" problems.

A slow first idea: quick-find

The simplest design stores for every element the label of its set, in a list.

TEXT
element: 0 1 2 3 4 5
label:   0 1 2 3 4 5        (everyone alone)

union(0, 1): relabel every 1 as 0
label:   0 0 2 3 4 5

union(1, 2): relabel every 0... as 2 (or 2 as 0)
label:   0 0 0 3 4 5

find is a single list lookup, O(1). But union has to scan the whole list to relabel, O(n). Merging n items one by one costs O(n^2). That is too slow for a million elements.

Python Quick-find: fast find, slow union

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The writes alone grow with the square of n. We want union to be cheap too.

The better idea: a forest of parent pointers

Store for each element a parent. A root points to itself. Each set is a tree, and the root is its representative.

TEXT
parent: [0, 0, 0, 3, 3, 5]

   0        3       5
  / \       |
 1   2      4

sets: {0, 1, 2}, {3, 4}, {5}
find(4): 4 -> 3 -> 3 is a root, so the answer is 3
  • find(x): follow parents until you reach an element that is its own parent.
  • union(a, b): find both roots; if they differ, make one root the parent of the other. That is a single assignment. No scanning.

The danger is tree height. If you always attach the first root under the second, a sequence like union(0,1), union(1,2), union(2,3), ... builds a tall chain, and find degrades to O(n). Two small tricks fix that.

Trick 1: union by size

When merging, attach the smaller tree under the larger one. A node's depth only increases when its tree is attached under a bigger one, which at least doubles the size of its set. A set can double at most log2(n) times, so no tree is ever taller than about log2(n). With this alone, both operations are O(log n). (Some books track rank, an upper bound on height, instead of size; the effect is the same.)

Trick 2: path compression

While walking up to the root in find, make every visited node point directly at the root (or, in the common cheaper variant, to its grandparent). The next find on any of those nodes takes one step.

TEXT
before find(5):        after find(5) with compression:

   0                        0
   |                     /  |  \
   1                    1   2   5     (3 and 4 are also flattened
   |                            if they were on the path)
   2
   |
   5

Used together, union by size and path compression make the cost per operation O(alpha(n)) amortized, where alpha is the inverse Ackermann function. It grows so slowly that it is below 5 for any input that could ever fit in a computer. In practice, treat it as constant time. (The proof is one of the beautiful results of amortized analysis.)

A complete implementation

Python Union-find with size and path compression

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The union method returns whether a merge actually happened. That boolean is the key to several problems below. Path halving is a loop version of path compression: it needs no recursion, so a long chain cannot hit Python's recursion limit.

A trace

Start with 8 singletons. union(0, 1): roots 0 and 1 have equal size, so 1 goes under 0 (the swap only happens if the first is smaller). union(1, 2): find(1) is 0, find(2) is 2; set 0 has size 2 and 2 has size 1, so 2 goes under 0. union(3, 4) makes 4 a child of 3. union(0, 2): both roots are 0, so nothing happens and the call returns False. Components so far: 8 - 3 = 5. The final union(2, 4) joins {0,1,2} and {3,4}: 4 components.

Why the tricks matter: counting steps

Do the tricks really help? Count how many parent pointers we follow while finding. We build a worst-case chain, then query every element.

Python Counting pointer steps with and without the tricks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without either trick, the structure is a chain of 1,000 nodes and the run follows 499,500 pointers, which is n(n-1)/2: the count grows with the square of n. With either trick it drops to 1,997, about two steps per operation. On this particular input the two tricks tie, because the unions arrive in a friendly order for each of them. Other inputs separate them, and that is why real implementations use both. Counting steps instead of seconds keeps the comparison independent of the computer.

Problem: redundant connection

You are given the edges of a graph that was a tree plus one extra edge, so it contains exactly one cycle. Return the extra edge, the one whose removal leaves a tree. If several choices exist, return the one that appears last in the list.

A brute force removes each edge in turn and checks with DFS whether the rest is a tree: O(E x (V + E)). Union-find does it in one pass: process the edges in order. If union(a, b) returns False, then a and b were already connected, so this edge closes a cycle. That is the answer.

Python Redundant connection

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This runs in O(E x alpha(V)), effectively linear. The same "does this edge join two already-connected vertices?" test is how Kruskal's algorithm skips edges that would form a cycle.

Union-find on names: merging accounts

Elements do not have to be integers. A dictionary-based union-find handles strings. Here several accounts list email addresses; two accounts belong to the same person if they share any email. Union all emails inside each account, then group.

Python Merge accounts that share an email

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Note the output lists emails sorted, since the order inside a dictionary of groups is an implementation detail we do not want to depend on.

Union-find or BFS/DFS?

Situation Better tool
Static graph, one component count DFS or BFS
Edges arrive over time, queries in between Union-find
Detect the first edge that closes a cycle Union-find
Need actual paths or distances BFS or Dijkstra
Edges can be deleted Neither directly (offline tricks exist)

Union-find only ever merges sets. It cannot split a set apart, and it does not remember which path connected two elements; it only knows that they are connected.

Common mistakes

  • Comparing the stored parents, not the roots. parent[a] == parent[b] is wrong for deep trees; always compare find(a) with find(b).
  • Linking elements instead of roots. parent[a] = b throws away the old structure of a's set. Always link find(a) and find(b).
  • Skipping union by size. Path compression alone gives O(log n) amortized, which is fine, but combining both is the standard.
  • Off-by-one with 1-based vertices. Allocate n + 1 slots when vertices are numbered from 1.
  • Forgetting the component count. Start from n and subtract one for each successful union.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does find(x) return in a union-find structure?

    Two elements are in the same set exactly when their find results (the roots) are equal.
  2. 2. In quick-find with a label array, what is the cost of a single union?

    Merging two sets requires relabeling every element of one set, which means scanning the array: O(n).
  3. 3. What does union by size guarantee?

    A node's depth only grows when its tree is attached under a tree at least as large, which at least doubles the size of its set, so a depth beyond log2(n) is impossible.
  4. 4. Using union-find, how do you recognize that an edge (a, b) creates a cycle in an undirected graph?

    If a and b are already connected through other edges, adding another edge between them closes a loop.
  5. 5. You start with 10 separate elements and perform 4 unions that all merge two different sets. How many sets remain?

    Each successful union reduces the set count by one, so 10 - 4 = 6.

Summary

  • Union-find (disjoint-set union) maintains disjoint sets under find (which set?) and union (merge two sets).
  • Store a parent pointer per element; the root of each tree represents its set. A union is one pointer assignment after two finds.
  • Union by size keeps trees short; path compression (or halving) flattens them. Together they make each operation O(alpha(n)) amortized, practically constant.
  • union returning False means the two elements were already connected, which detects cycles and redundant edges in a single pass.
  • The structure works on any hashable elements if you use a dictionary for the parents.
  • It only merges; use BFS/DFS when you need paths or distances, and a different technique when edges are deleted.

Next: Dijkstra's Algorithm