Graphs

13 questions — the largest section after Trees, and the one where recognising which standard traversal applies is most of the work.

Seven of thirteen are grids

A grid is a graph you never have to build

Each cell is a node; its four neighbours are its edges, computed arithmetically. With V = m·n and E ≤ 4V, every traversal is O(m·n). No adjacency list is ever built.

Choosing the traversal

Question shape	Algorithm	Questions
Count / measure components	DFS or BFS flood	1, 2, 11
Shortest path, unweighted	BFS	13
Distance to the nearest of many sources	multi-source BFS	4, 5
Copy a structure with cycles	DFS/BFS + a map	3
Cycle detection, directed	3-colour DFS or Kahn's	8, 9
Cycle detection, undirected	union-find, or DFS with a parent check	10, 12
Reachability for every cell	reverse the search	6, 7

DFS vs BFS for pure reachability is a genuine trade: O(depth) stack against O(width) queue. At 300 × 300 an all-land grid is one 90,000-cell island, which overflows the default JVM stack — so BFS is the safe default at that size.

Multi-source BFS

Seeding every source at distance 0 turns O(sources · m · n) into O(m · n). It's correct because BFS expands in order of distance from the seed set, so a cell's first arrival is already its minimum — no cell ever needs updating.

Questions 4 and 5 are the same algorithm; only what you record differs (a per-cell distance vs a level count).

Reversing the question

Start from the oceans, not from the cells

When "can X reach the target?" must be answered for every X, invert it to "what can the target reach?". One traversal replaces n of them — O((m·n)²) → O(m·n).

The reversal needs the relation to be invertible. In Pacific Atlantic, A → B iff height[A] >= height[B], which reads identically backwards. Surrounded Regions applies the same idea to a membership test: "surrounded" is hard to check, "touches the border" is trivial, and everything unmarked is surrounded by definition.

Cycle detection needs three states

A plain visited set conflates "on my current path" with "already finished". Only the first is a cycle.

Verified: on the acyclic diamond A→B, A→C, B→C, a two-state check reports a cycle. Three colours correctly report none.

And in an undirected graph the problem is different again — every edge looks like a back-edge to its own parent — so you track the parent or use union-find, which has no notion of direction.

Union-Find

Two independent optimisations: union by size stops deep chains forming, path compression flattens whatever chains exist. Either alone gives O(log n); together, O(α(n)) — inverse Ackermann, below 5 for any n that fits in the universe. Effectively constant, not literally so.

The same test means different things in three questions:

`find(u) == find(v)`	Meaning	Question
reject	a cycle — not a tree	10
skip	a redundant edge; count unchanged	11
return it	this is the redundant edge	12

Medium Number of Islands LC 200 11 min Medium Max Area of Island LC 695 10 min Medium Clone Graph LC 133 11 min Medium Walls and Gates LC 286 10 min Medium Rotting Oranges LC 994 11 min Medium Pacific Atlantic Water Flow LC 417 12 min Medium Surrounded Regions LC 130 11 min Medium Course Schedule LC 207 13 min Medium Course Schedule II LC 210 12 min Medium Graph Valid Tree LC 261 13 min Medium Number of Connected Components in an Undirected Graph LC 323 11 min Medium Redundant Connection LC 684 12 min Hard Word Ladder LC 127 13 min

The `n − 1` edge theorem

A connected graph needs at least n − 1 edges; an acyclic one has at most n − 1. So with exactly n − 1, connected ⟺ acyclic — check either and you've proved both.

But n − 1 edges alone proves nothing: a triangle plus an isolated node has n − 1 edges and is neither connected nor acyclic.

Word Ladder: the adjacency is the bottleneck

BFS gives the shortest path when every edge costs 1

The BFS is standard. Comparing every pair of words to find neighbours is O(N² · L) = 2.5 × 10^8; bucketing by wildcard pattern (h*t, ho*, *it) is O(N · L²) = 5 × 10^5. Roughly 500×, and it's why the problem is Hard.

The traps

Trap	Symptom
DFS on a 300×300 all-land grid (Q1)	90,000 frames — stack overflow
Marking visited on dequeue, not enqueue	Duplicates in the queue; work multiplies
Not registering the copy before recursing (Q3)	Infinite recursion on any undirected edge
Counting `-1` for zero fresh oranges (Q5)	Should be 0
Missing the level snapshot (Q5)	Everything rots in one minute
Inverting the height comparison (Q6)	Plausible wrong answer, not a crash
`
Two-state cycle detection (Q8)	Reports cycles in DAGs
Iterating edges, not nodes (Q11)	Isolated nodes uncounted
`int[n]` for 1-indexed nodes (Q12)	Index out of bounds on node `n`
Pairwise word comparison (Q13)	`O(N²·L)` — times out

Verification

Every snippet compiled and cross-checked against an independent implementation — 4,300+ randomized cases:

Q1 across DFS, BFS and union-find
Q3 verified structurally: the clone shares no node with the original, and the neighbour correspondence is bijective
Q4 against a per-room BFS; Q5 against a whole-grid simulation
Q6 against a forward per-cell DFS — the O((m·n)²) version the optimal replaces
Q8/Q9 with Kahn's and three-colour cross-checked, and every returned order independently re-verified as a valid topological sort
Q12 against a remove-and-test reference, confirming the tie-break claim: union-find's first hit really is the last valid edge
Q13 with wildcard buckets checked against pairwise comparison

One deliberately-broken variant confirms the headline trap: a two-state cycle check reports a cycle on the acyclic diamond 0→1, 0→2, 1→2.