Union-Find (DSU) · bigonotes

Union-Find, also called a Disjoint Set Union (DSU), keeps items in non-overlapping groups and answers one question fast: are these two in the same group? It's the right tool when connections arrive one at a time and you need the answer after each one. It tells you whether two items are connected, never the path between them.

The idea#

Every group has one leader, the boss (root). Each item stores a parent pointer, and following parents upward always ends at the boss. Two items are connected exactly when they have the same boss.

find(x) walks up to the boss. Path compression makes every item on the way point straight at the boss, so later lookups are almost instant.
union(x, y) finds both bosses. If they differ, one boss reports to the other, and the number of groups drops by one. If they are the same, the two items were already connected.

That second case is the useful one for cycles: in an undirected graph, an edge whose ends already share a boss closes a loop.

How to spot it#

Reach for DSU when the problem is about groups rather than paths.

Cue	Example
Connectivity, groups, components, "how many groups are left?"	Number of Provinces, Network Connected
Undirected cycle: "find the edge that creates a loop"	Redundant Connection
Equivalence and transitivity: `a == b`, `b == c`, so `a == c`	Satisfiability of Equality Equations
Merging records that share an attribute	Accounts Merge (shared emails)
Connections arriving over time (dynamic connectivity)	DSU instead of re-running DFS each time

Template#

The count field answers "how many groups?", which a large share of DSU questions ask. union returns true or false so you can detect cycles.

parent[x] = x for every item           # each item is its own boss
count = n                              # number of separate groups
find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])    # path compression
    return parent[x]
union(x, y):
    root_x = find(x); root_y = find(y)
    if root_x == root_y: return false  # already connected: a cycle
    parent[root_x] = root_y
    count -= 1
    return true

Most DSU problems end with one of these checks:

Return count: how many groups are there?
union returned false: this edge makes a cycle.
Valid tree: len(edges) == n - 1 and count == 1 at the end.

With path compression, each operation is close to constant time amortized. (The tight $O(\alpha(n))$ bound also needs union by rank or size. Here $\alpha$ is the inverse Ackermann function, which grows so slowly that it is effectively constant.) Scanning an $n \times n$ adjacency matrix still costs $O(n^2)$ , because you have to read the input.

Keys that aren't 0..n-1#

When the items are strings, coordinates or very large numbers, swap the list for a dict that creates entries lazily. Only find changes.

parent = empty map
find(x):
    if x not in parent: parent[x] = x  # first sight: its own boss
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

Counting successful unions#

Sometimes the answer is the number of unions that merge two groups. A union of two items that already share a boss costs nothing. This comes up in the palindrome-by-renaming variation at the end of the hints. Each trace below pairs data[i] with its mirror data[n - 1 - i] and counts the merges.

Array	Mirror pairs	Successful unions
`[1, 2, 3, 3, 1, 4]`	(1,4), (2,1), (3,3)	2
`[1, 3, 5, 2, 1]`	(1,1), (3,2)	1
`[2, 4, 5, 7, 4, 5, 5]`	(2,5), (4,5), (5,4)	2

Pitfalls#

These are the mistakes that most often cost a correct answer.

Comparing parent[x] == parent[y] instead of find(x) == find(y); parents are not bosses until compressed.
Unioning raw values instead of their roots (parent[x] = y instead of parent[find(x)] = find(y)).
Letting two kinds of key collide when they share one DSU (for example a row number and a column number).
Checking "must differ" constraints before every "must be equal" union has been applied.
Treating "union returned false" as a cycle in a directed graph; DSU cycle detection only works for undirected edges.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Number of Provinces

Union every pair the matrix marks as connected, then return count. Reading the $n \times n$ matrix already costs $O(n^2)$ .

Hint: Redundant Connection

Add the edges in order. The first union that returns false joins two nodes that already share a boss, so that edge closes the cycle.

Hint: Number of Operations to Make Network Connected

You need at least $n - 1$ cables to connect $n$ computers, so return -1 if there are fewer. Otherwise every spare cable can be moved, and the answer is components - 1.

Hint: Accounts Merge

Union account indices, not emails. Keep a map from each email to the first account index that owned it, and union when the email shows up again. Then group every email under find(owner[email]) and sort each group with plain sorted(); sorting dominates at $O(E \log E)$ for $E$ emails.

Hint: Satisfiability of Equality Equations

Do the unions first: process every == and union both letters. Then check each !=: if both letters share a boss, an earlier equality forces them equal, so the input is contradictory. Checking before all the unions are in misses contradictions.

Hint: Most Stones Removed with Same Row or Column

Each stone joins its row to its column, and every group can be cleared down to one stone, so the answer is stones - number_of_groups. Row 5 and column 5 must be different keys. Use union(x, ~y) (for y >= 0, ~y = -y - 1 is negative) or tuple keys with the dict-based DSU, or an offset such as y + 10001 into a fixed array of size 20002 when coordinates are at most 10,000.

Hint: Greatest Common Divisor Traversal

Two indices connect when their values share a prime factor. Union each index with its prime factors, then check that everything ends up in one component.

Hint: Palindrome by renaming (variation)

One operation replaces every x with y; find the fewest operations to make the array a palindrome. data[i] and data[n - 1 - i] must end up equal, so union each mirror pair and count only the successful unions. Equivalently, a group of $k$ values needs $k - 1$ renames.

Hint: Find if Path Exists in Graph

Union the two ends of every edge, then check whether source and destination have the same root. BFS works too; solving it both ways shows when union-find is the simpler tool.

Key takeaways#

Same boss means same group; path compression keeps find nearly constant.
union returning false means the edge closes an undirected cycle.
Track count to answer "how many groups?" for free.
Use a dict-based DSU, with ~y or tuple keys, when keys aren't small integers.
DSU hides in non-graph problems wherever "these must become the same" relations chain together.

Core idea#

Union-Find (DSU) keeps items in non-overlapping groups and answers "are these two in the same group?" fast. It tells you whether two items connect, never the path.

Key points#

Each group has one boss (root). Same boss means same group.
find walks up to the boss. Path compression points every item on the way at the boss.
union joins two bosses and lowers count by one.
union returning false means the edge closes an undirected cycle.
Valid tree: len(edges) == n - 1 and count == 1.
Each operation is near constant amortized. The tight $O(\alpha(n))$ bound also needs union by rank or size.
Keys that are not 0..n-1: use a dict with parent.setdefault(x, x).

Spot it#

Cue	Example
How many groups are left	Number of Provinces
Edge that creates a loop	Redundant Connection
`a == b`, `b == c`, so `a == c`	Equality Equations: all `==` first, then `!=`
Records that share an attribute	Accounts Merge: union account indices
Rows and columns as keys	Most Stones: `stones - groups`, keys `x` and `~y`
Spare cables	Network Connected: -1 if fewer than n − 1, else `components - 1`

Template#

parent[x] = x for every item; count = n
find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])    # path compression
    return parent[x]
union(x, y):
    root_x = find(x); root_y = find(y)
    if root_x == root_y: return false  # closes a cycle
    parent[root_x] = root_y
    count -= 1
    return true

Pitfalls#

Comparing parent[x] == parent[y] instead of find(x) == find(y).
Writing parent[x] = y instead of parent[find(x)] = find(y).
Letting row and column keys collide.
Checking != before every == union is applied.
Using DSU cycle detection on a directed graph.

Say it in an interview#

"Union-Find answers connectivity as edges arrive, in near-constant time."
"If both ends already share a boss, this edge makes a cycle."