Recognising the Pattern

DSU is easy to implement and hard to notice. The structure almost never appears in the problem statement - what appears is a story about friend circles, provinces, equations, stones, or islands, and the word "graph" is often absent entirely. This page is the recognition half: the phrases that mean DSU, the encodings that make non-integer elements usable, and the three transformations that turn a problem that is not about connectivity into one that is.

1. The trigger phrases

If a problem contains one of these, DSU is at least a candidate.

The statement says	It is asking for
	Canonical problem
"how many groups / circles / provinces / islands"	dsu.count after absorbing every edge
	Number of Provinces, Number of Connected Components, Number of Islands
"are a and b connected / related / equal"	find(a) == find(b)
	Find if Path Exists, Sentence Similarity II
"the largest group / the size of x's group"	size metadata on the roots
	Max Area of Island, Merging Communities
"which edge can be removed / makes it invalid"	the first edge whose union returns False
	Redundant Connection, Graph Valid Tree
"is this set of statements consistent"	union the equalities first, then check every inequality
	Satisfiability of Equality Equations
"the earliest time everyone is connected"	sort events by time, union until count == 1
	The Earliest Moment When Everyone Become Friends
"minimum cost to connect everything"	Kruskal: sort edges, union, keep the ones that return True
	Min Cost to Connect All Points, MST
"transitively", "indirectly", "through a chain of"	the giveaway word - transitive closure of a symmetric relation is DSU
	every problem in this section

Mnemonic

"Transitively" and "eventually connected" are the two words that mean DSU out loud. A relation that is reflexive, symmetric and transitive is an equivalence relation, and a disjoint-set structure is the data structure for exactly one of those. If you can convince yourself the relation in the problem is symmetric, DSU applies; if it is not, it does not.

2. DSU or traversal?

Both answer "how many components" in linear time, so the choice is decided by the other things the problem needs.

DSU or BFS/DFS

Full

Quiz

does the problem ask about groups / connectivity?

no

not DSU

yes

do you need the path, the distance, or the order?

yes

BFS / DFS

no - just "same group?" or "how many groups"

do edges arrive over time, or get removed?

arrive over time / streamed

DSU

get removed

DSU, backwards

all given up front, static

either

	DSU	BFS / DFS
edges arrive one at a time	natural - absorb each as it comes	must rebuild and re-traverse
need the path or the distance	impossible	natural
directed reachability	wrong answer (computes weak connectivity)	correct
need the members of each group	one extra O(n) pass	natural, you have them while walking
grid of cells	works, needs an index encoding	usually simpler
need an MST	Kruskal is DSU	Prim is a traversal with a heap
answer is "does adding this break it"	the union return value	a fresh cycle check per edge

⚠

A grid problem is usually not a DSU problem

Islands-family problems are solvable with DSU and are almost always cleaner with BFS/DFS. The grid already gives you neighbours for free, so the adjacency-list argument for DSU disappears, and you pay an index encoding (r * cols + c) for nothing. Reach for DSU on a grid only when the cells arrive over time - "add land one at a time and report the island count after each" is the case where a traversal would restart from scratch and DSU would not.

3. Making the elements integers

DSU wants elements 0 .. n-1. Real problems hand you strings, coordinate pairs, or sparse numbers. Three encodings cover almost everything.

Three ways in. All three end with a dense integer index, which is the only thing the array-backed DSU understands.

The interning idiom, which is worth having in muscle memory:

ids = {}

def idx(key):

return ids.setdefault(key, len(ids)) # first sight assigns the next index

 

for a, b in pairs:

dsu.union(idx(a), idx(b))

Size the DSU up front at the maximum possible element count (2 * len(pairs) is always safe for pairs), or use a dict-backed DSU that grows on demand.

Backing	Use when
	Cost
Array parent = list(range(n))	elements are already integers in a bounded range, or you interned them into one
	Fastest. Cache-friendly, no hashing. The default.
Dict parent = {}	keys are strings or tuples and you would rather not intern, or you genuinely do not know n in advance
	Roughly 3-5x slower per operation, and find has to lazily insert unseen keys. Fine at interview scale.

Array or HashMap

Full

Quiz

are elements integers in [0, n)?

yes -- dense indices

array

no

can you map them to a small integer range yourself?

yes

array

no -- strings, tuples, sparse coords

hashmap

Two problems sit right on that boundary: Most Stones Removed encodes (row, col) as col + 10001 to keep the range bounded, so an array works; Smallest String with Swaps unions character indices, also an array - but if the keys had been arbitrary strings, both would need a dict.

⚠

r * cols + c, never r * rows + c

The flattening multiplier is the number of COLUMNS. Using rows gives a mapping that is not injective whenever the grid is not square: two different cells collide onto one index, and the DSU merges groups that were never adjacent. Square test grids pass. Write r * len(grid[0]) + c and the question never comes up.

4. The virtual node trick

Some problems want "connected to the outside", "connected to any of these sources", or "attached to the power grid". Adding one extra element that is not in the input turns all of those into ordinary unions.

Instead of asking whether any of several cells is connected to the top edge, union them all with one virtual node and ask about it.

Problem shape	The virtual node
	Buys you
several sources, "reachable from any"	one node unioned to every source
	k separate checks collapse into one find
percolation: "does water reach the bottom"	one node for the top edge, one for the bottom
	the answer is a single find(top) == find(bottom)
"enemies must be apart" over n people	2n elements: i means "i on side A", i + n means "i on side B"
	union(a, b+n) and union(b, a+n) per conflict; a contradiction is find(i) == find(i+n)
groups defined by a shared attribute (same row, same prefix, same factor)	one node per attribute value, unioned with every element carrying it
	avoids the O(n^2) "union every pair that shares an attribute" blowup

Mnemonic

When you are about to write a loop that unions every pair sharing a property, add a node for the property instead. n elements sharing a property cost n unions through a hub, versus n^2 / 2 unions pairwise. Most Stones Removed and the "same row or same column" family are exactly this.

The 2n construction deserves its own note: it is the poor man's parity DSU. Doubling the element count and reading i + n as "not i" gets you opposite-side reasoning with a completely unmodified DSU, at the cost of twice the memory and slightly more thinking at the call site. Parity DSU is the same idea done properly.

5. Running time backwards

DSU merges and never splits. So when a problem removes things - cuts cables, deletes nodes, floods cells - process the events in reverse and reverse the answers at the end. Every removal becomes an addition, which DSU handles natively.

# "after each removal, how many components remain?"

answers = []

for event in reversed(removals):

dsu.union(*event) # a removal, read backwards, is a merge

answers.append(dsu.count)

answers.reverse()

Forwards, the problem says	Backwards, it becomes
remove an edge	add an edge
a cell floods / becomes blocked	a cell becomes usable
"the last day the network is still connected"	"the first day, going backwards, that count hits 1"
"components after each deletion"	"components after each insertion", then reverse the list

Mnemonic

Offline plus deletions means run it backwards. The precondition is that you can see all the queries in advance ("offline"). If the queries are truly online - each depends on the previous answer - you cannot reverse, and you need rollback DSU or a link-cut tree instead.

6. Sorting first: Kruskal and its relatives

A second family feeds the edges to DSU in a chosen order rather than the given one, and lets the union return value do the filtering.

edges.sort(key=lambda e: e[2]) # by weight

total = 0

for u, v, w in edges:

if dsu.union(u, v): # True means it joined two components

total += w # so it belongs in the MST

That is Kruskal's algorithm in five lines, and the same skeleton with a different sort key solves a surprising range:

Sort by	And you get
	Example
weight, ascending	the minimum spanning tree
	Min Cost to Connect All Points, Connecting Cities With Minimum Cost
weight, descending	the maximum spanning tree, i.e. the bottleneck path
	"maximise the minimum edge on a route" - stop as soon as the two endpoints connect
time / day, ascending	the first moment the whole thing is connected
	The Earliest Moment When Everyone Become Friends
a query threshold, ascending	offline query answering: absorb every edge under the threshold, then answer
	"are a and b connected using only edges lighter than limit"

Mnemonic

Sort the edges, then let union say yes or no. Every problem in this family is "process in some order and keep what merges." Once you see the skeleton, the only decision left is the sort key.

7. The checklist

Before writing a DSU solution, five questions. Each maps to a bug that is easy to make and hard to spot.

#	Question	If you get it wrong
1	Is the relation symmetric? Would the problem accept b related to a too?	On a directed graph you silently compute weak connectivity.
2	How many elements, and are they dense integers? What is n for list(range(n))?	Index out of range, or a needlessly enormous array.
3	Do you need sizes, counts, or a specific representative? Add the metadata before writing union.	Retrofitting metadata means touching every branch of union.
4	Do edges get removed? Then reverse time, or use rollback.	You reach for a split operation that does not exist.
5	Do you need the members, a path, or a distance? Then DSU is half the solution at most.	You finish the DSU and discover it cannot answer the actual question.

Next: Variants - parity, weights, and rollback, for the problems where "same group" is not enough.