Union-Find Problem Patterns

DFS and BFS answer connectivity questions in $O(V + E)$ — but only for a graph that is fully built. If edges arrive one at a time and you must answer “are these two connected?” after each one, traversal means re-running the whole search per query.

Union-find (disjoint set union) is the structure for that. It maintains connectivity incrementally, and both operations run in almost constant time.

The Union-Find data structure page covers how it works. This page is about recognising when a problem wants one, and the four shapes those problems take.

What you’ll learn

The 20-line implementation worth memorising, with both optimisations.
The unionunion return value that turns the structure into a cycle detector.
Maintaining a component count for free.
When union-find beats DFS — and the several cases where it does not.
Three real LeetCode problems solved in the browser: 547, 684, 1319.

The cue

Edges arrive incrementally and you answer queries between additions — 305, 1101.
”How many groups / provinces / components” after processing all relations — 547, 323, 1319.
Detect the edge that creates a cycle in an undirected graph — 684.
Items must be merged by shared attributes, transitively — 721 Accounts Merge, 839 Similar String Groups.
Constraints must be checked for consistency — 990 equality equations.
Kruskal’s MST, where union-find is the mechanism that rejects cycle-forming edges.

The anti-cue — important: union-find only tracks whether things are connected. It cannot give you a path, a distance, or handle deletions. It also does not work naturally on directed graphs. If you need any of those, use BFS/DFS or topological sort instead.

The implementation

Two optimisations turn a potentially $O(n)$ tree walk into effectively $O(1)$ . Both are one line each and neither is optional in an interview.

dsu.py

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))     # each node starts as its own root
        self.rank = [0] * n              # tree height, for union by rank
        self.components = n              # every node is its own component
 
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x
 
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                 # ALREADY connected -> this edge is a cycle
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra              # attach the shorter tree under the taller
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.components -= 1
        return True                      # a genuine merge happened
 
    def connected(self, a, b):
        return self.find(a) == self.find(b)

dsu.py

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))     # each node starts as its own root
        self.rank = [0] * n              # tree height, for union by rank
        self.components = n              # every node is its own component
 
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x
 
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                 # ALREADY connected -> this edge is a cycle
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra              # attach the shorter tree under the taller
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.components -= 1
        return True                      # a genuine merge happened
 
    def connected(self, a, b):
        return self.find(a) == self.find(b)

Path compression (here as path halving: parent[x] = parent[parent[x]]parent[x] = parent[parent[x]]) flattens the tree as you walk it, so later findfind calls on the same chain are short. Without it, a degenerate chain makes findfind $O(n)$ .

Union by rank attaches the shorter tree under the taller one, so trees never get needlessly deep. Without it, repeatedly unioning in the wrong order builds exactly the chain that path compression then has to repair.

Together they give an amortised cost of $O(\alpha(n))$ where $\alpha$ is the inverse Ackermann function — below 5 for any nn you will ever see, so effectively constant. Saying “effectively $O(1)$ , formally $O(\alpha(n))$ amortised” is the answer interviewers are listening for.

Path halving is written iteratively above, which avoids recursion-limit problems on large inputs. Full path compression via recursion (parent[x] = find(parent[x])parent[x] = find(parent[x])) is equally acceptable and slightly more aggressive.

Complexity, versus the alternatives

Task	Union-find	DFS / BFS
Count components (static graph)	$O(E \cdot \alpha)$	$O(V + E)$ — equally good
Connectivity query after each new edge	$O(\alpha)$ per query	$O(V + E)$ per query
Find a cycle-creating edge	$O(E \cdot \alpha)$	$O(V + E)$ with parent tracking
Shortest path	❌ impossible	✅ BFS
Handle edge deletion	❌ not supported	✅ rebuild
Directed graphs	❌ not naturally	✅

For a static graph, DFS is just as good and often simpler — LC 547 is perfectly solvable either way. Union-find wins decisively when the graph grows over time.

The variant map

Variant	What you read off	Canonical problem
Count components	`dsu.componentsdsu.components` after all unions	547 · 323
Detect the cycle edge	The first `unionunion` returning `FalseFalse`	684
Count merges needed	`components - 1components - 1`	1319
Merge by shared attribute	Union items sharing a key, then group by root	721 Accounts Merge
Consistency check	Union equalities first, then test inequalities	990
Incremental islands	`componentscomponents` maintained as land is added	305
Kruskal’s MST	Union edges in weight order, skipping cycles	MST

Practice — real LeetCode problems

LC 547 — Number of Provinces · Medium

Problem. Given an n x nn x n adjacency matrix isConnectedisConnected where isConnected[i][j] == 1isConnected[i][j] == 1 means cities ii and jj are directly connected, return the number of provinces (connected components).

Constraints. 1 <= n <= 2001 <= n <= 200, the matrix is symmetric with isConnected[i][i] == 1isConnected[i][i] == 1.

Examples. [[1,1,0],[1,1,0],[0,0,1]][[1,1,0],[1,1,0],[0,0,1]] gives 22 · [[1,0,0],[0,1,0],[0,0,1]][[1,0,0],[0,1,0],[0,0,1]] gives 33 · [[1]][[1]] gives 11

Editorial — approach, complexity, follow-ups

Begin with nn singleton components and merge each connected pair. Because unionunion only decrements when a genuine merge happens, the counter is exact at the end — no need to count distinct roots afterwards.

Time $O(n^2 \cdot \alpha(n))$ — dominated by reading the $n^2$ matrix. Space $O(n)$ .

Two details:

Upper triangle only. The matrix is symmetric, so jj starts at i + 1i + 1. This also skips the diagonal, where isConnected[i][i] == 1isConnected[i][i] == 1 would attempt a self-union — harmless (find(i) == find(i)find(i) == find(i), so unionunion returns FalseFalse) but pointless work.
componentscomponents beats counting roots. The alternative, len({find(i) for i in range(n)})len({find(i) for i in range(n)}), is also correct and is a fine fallback if you did not maintain a counter.

DFS is equally valid here and arguably simpler, since the graph is static: iterate nodes, and for each unvisited one run a DFS marking its whole component, counting how many DFS runs you start. Say this. Union-find is the better answer only if the follow-up adds edges over time.

Follow-ups you should expect: “Do it with DFS” — have it ready. “What if the input were an edge list instead of a matrix?” — $O(E \alpha)$ instead of $O(n^2)$ , a strict improvement for sparse graphs. “What if cities could be disconnected later?” — union-find cannot un-merge; you would rebuild, or use a link-cut tree. “Return the size of the largest province?” — maintain a sizesize array alongside rankrank.

LC 684 — Redundant Connection · Medium

Problem. A tree with nn nodes had one extra edge added, creating exactly one cycle. Given the edge list, return the edge that can be removed so the graph is a tree again. If several answers exist, return the one appearing last in the input.

Constraints. 3 <= n <= 10003 <= n <= 1000, nodes are labelled 1..n1..n, no duplicate edges and no self-loops.

Examples. [[1,2],[1,3],[2,3]][[1,2],[1,3],[2,3]] gives [2,3][2,3] · [[1,2],[2,3],[3,4],[1,4],[1,5]][[1,2],[2,3],[3,4],[1,4],[1,5]] gives [1,4][1,4]

Editorial — approach, complexity, follow-ups

A tree on nn nodes has exactly n - 1n - 1 edges. With one extra edge there is exactly one cycle, and the redundant edge is any edge on that cycle.

Union the edges in the given order. Every edge that merges two distinct components is a genuine tree edge. The first edge whose endpoints are already connected must close the cycle — and because we scan left to right, that first failure is also the last cycle edge in input order, which is exactly what the problem asks for.

Time $O(n \cdot \alpha(n))$ . Space $O(n)$ .

The tidy part is that “return the last valid answer” needs no extra work: the scan order gives it. If you had instead collected all cycle edges and picked the latest, you would be doing more work for the same result.

1-indexing is the practical trap: sizing the arrays nn instead of n + 1n + 1 gives an IndexErrorIndexError on node nn.

A DFS solution also exists — add edges one at a time and check whether a path already exists between the endpoints — but that is $O(n)$ per edge, so $O(n^2)$ overall. Union-find is the reason this is Medium rather than tedious.

Follow-ups you should expect: “What if the graph were directed (LC 685)?” — genuinely harder, and union-find alone is insufficient: you must also handle a node with two parents, so you consider up to two candidate edges and test each. Knowing that the directed version is a different problem is the useful insight. “What if there were multiple extra edges?” — return all edges whose union fails. “Detect whether a cycle exists at all?” — any failed union.

LC 1319 — Number of Operations to Make Network Connected · Medium

Problem. There are nn computers and a list of connectionsconnections (cables). You may unplug any cable and replug it elsewhere. Return the minimum number of such moves to connect all computers, or -1-1 if impossible.

Constraints. 1 <= n <= 10^51 <= n <= 10^5, 1 <= len(connections) <= min(n * (n - 1) / 2, 10^5)1 <= len(connections) <= min(n * (n - 1) / 2, 10^5), no duplicate connections.

Examples. n = 4, connections = [[0,1],[0,2],[1,2]]n = 4, connections = [[0,1],[0,2],[1,2]] gives 11 · n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]] gives 22 · n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]n = 6, connections = [[0,1],[0,2],[0,3],[1,2]] gives -1-1

Editorial — approach, complexity, follow-ups

Two independent observations, and separating them is the whole solution:

Feasibility. A connected graph on nn nodes needs at least n - 1n - 1 edges. Fewer cables than that and no rearrangement can help, so -1-1.
Cost. With enough cables, union everything and count the remaining components cc. Joining cc groups into one takes exactly c - 1c - 1 moves.

Why the moves are always available: if len(connections) >= n - 1len(connections) >= n - 1 and there are cc components, then some cables must be redundant (inside a component that already spans its nodes). Precisely those spares can be unplugged and used for the c - 1c - 1 bridges. So the count of components alone determines the answer — you never need to identify which cables are redundant.

Time $O(E \cdot \alpha(n))$ . Space $O(n)$ .

(6, [[0,1],[0,2],[0,3],[1,2]])(6, [[0,1],[0,2],[0,3],[1,2]]) returning -1-1 is the feasibility case: 4 cables for 6 computers, and 5 are required.

Follow-ups you should expect: “Prove the spare cables always exist” — the counting argument above; this is the likely probe. “Which cables would you move?” — any edge whose unionunion returned FalseFalse. “What if cables had lengths and you wanted minimum total?” — that is Kruskal’s MST, with union-find as the engine. “Could you use DFS?” — yes, count components with DFS and subtract one; union-find is not required for a static graph.

LeetCode problem set

#	Problem	Difficulty	The twist
547	Number of Provinces	Medium	Component counting; DFS is equally fine here
684	Redundant Connection	Medium	The first failed `unionunion` is the cycle edge
1319	Number of Operations to Make Network Connected	Medium	Cable count for feasibility, component count for cost
721	Accounts Merge	Medium	Union accounts sharing an email; map strings to indices, then group by root
990	Satisfiability of Equality Equations	Medium	Union all `====` first, then check every `!=!=`
128	Longest Consecutive Sequence	Medium	Solvable with union-find, but a hash set is simpler and also $O(n)$

Interview follow-ups

They ask	What they’re checking	The answer
“Union-find or DFS?”	Judgement	DFS is equally good on a static graph; union-find wins when edges arrive incrementally and you answer queries between them
“What’s the complexity?”	Precision	$O(\alpha(n))$ amortised per operation with both optimisations — effectively constant, since $\alpha(n) < 5$ for any realistic `nn`
“Name the two optimisations”	Whether you know why it is fast	Path compression (flatten during `findfind`) and union by rank/size (attach shorter under taller). Either alone is worse
“How do you detect a cycle?”	The key idiom	A `unionunion` that finds both endpoints already sharing a root
“Can you delete an edge?”	Knowing the limits	No — union-find is merge-only. Rebuild, or use a link-cut tree
“Does it work on directed graphs?”	Limits again	Not naturally; use topological sort or DFS colouring for directed cycles
“Keys are strings, not ints”	Practical adaptation	Map to indices with a dict, or use a dict-based `parentparent` that grows lazily
“Track component sizes?”	Extensibility	Keep a `sizesize` array and add it during `unionunion` — cheap and often asked

Edge-case checklist

Single node — n = 1n = 1; one component, zero operations.
No edges at all — nn components; LC 1319 returns -1-1 unless n == 1n == 1.
All nodes already connected — components == 1components == 1; answer 00.
Self-loops — union(i, i)union(i, i) returns FalseFalse harmlessly, but do not count it as a cycle if the problem excludes self-loops.
Duplicate edges — the second one fails its union; whether that counts as a “cycle” depends on the problem.
1-indexed nodes — size the arrays n + 1n + 1 (LC 684). A frequent IndexErrorIndexError.
Not enough edges — LC 1319’s feasibility check must come first.
Ordering of constraints — LC 990 needs all equalities before any inequality.

Recap

Union-find maintains connectivity incrementally in effectively $O(1)$ — formally $O(\alpha(n))$ amortised with both optimisations.
Path compression plus union by rank are both required; either alone leaves a bad worst case.
unionunion returning FalseFalse means a cycle — that boolean solves LC 684 outright.
Maintain a componentscomponents counter and decrement per successful merge; no final root-counting pass needed.
“Join cc groups” always costs c - 1c - 1 merges.
For static graphs, DFS is equally good — say so. Union-find’s edge is incremental edges and repeated queries.
It cannot give paths or distances, cannot delete edges, and does not suit directed graphs. Know those limits before reaching for it.

Next: Shortest Paths — Dijkstra, Bellman-Ford and Floyd-Warshall, for when edges carry weights and you need distances rather than just connectivity.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Union-Find Problem Patterns

What you’ll learn

The cue

The implementation

Complexity, versus the alternatives

The variant map

Practice — real LeetCode problems

LC 547 — Number of Provinces · Medium

LC 684 — Redundant Connection · Medium

LC 1319 — Number of Operations to Make Network Connected · Medium

LeetCode problem set

Interview follow-ups

Edge-case checklist

Recap

Was this page helpful?