These are my data structures and algorithms notes, cleaned up into nineteen posts, one pattern at a time. This one covers graphs: grids and adjacency lists, depth-first and breadth-first search on both, three-colour cycle detection with the ordering it gives for free, and Union-Find, followed by the thirteen problems they unlock.
A graph is what you get when you stop assuming your data is a line (arrays), a chain (linked lists) or a hierarchy (trees). Things connect to other things, possibly in loops, possibly in several disconnected pieces, and the question is almost always some version of “what can I reach from here, how fast, and in what order”. The traversal itself is not new. It’s the DFS and BFS from Trees and the mark-and-explore recursion from Backtracking, with one addition trees never needed: a record of where you’ve already been, because a graph can lead you back to a vertex you’ve already visited.
The prerequisites here are Intro to Graphs, Matrix DFS, Matrix BFS and Adjacency List. The problem list also needs two things those don’t teach. Directed cycle detection and ordering are folded into Adjacency List here. Union-Find gets its own short module at the end. Graphs comes after Backtracking in the order this series follows, and unlocks Advanced Graphs (weighted shortest paths, spanning trees, the full topological sort) and 2-D DP.
How to use this post: the method. Checkpoints have no answers on the page: work them out, then open the linked chat to have your answer checked.
Intro to Graphs
Foundation
A graph is a set of vertices (nodes) and a set of edges (connections between pairs of vertices). That’s the whole definition. Everything else is a property of the edges:
- Directed or undirected. A follow on a social network is directed (I follow you, you might not follow me). A friendship is undirected. An undirected edge is just a directed edge in both directions.
- Cycles. A path that returns to its start. Trees are exactly the graphs where this can’t happen.
- Connected components. The separate pieces. A graph doesn’t have to be one piece.
With V vertices there are at most V² directed edges, so E can be anywhere from 0 to roughly V². That range is why representation matters.
Mechanics
Interview problems hand you graphs in three shapes:
- A grid (matrix). Each cell is a vertex, and its neighbours are the cells up, down, left and right. The edges are never stored. You compute them from
(r ± 1, c)and(r, c ± 1)when you need them. - An adjacency matrix. A V × V table where
matrix[u][v] == 1means an edge u → v. Checking one edge is O(1), but the table always costs V² memory, however few edges there are. - An adjacency list. For every vertex, a list of its neighbours. It costs O(V + E) memory and makes “iterate over u’s neighbours” cost exactly deg(u). This is what you build from an edge list almost every time.
The worked example for this module: n = 5 vertices, undirected edges [[0, 1], [0, 2], [1, 2], [3, 4]].
The key property: in an undirected adjacency list, every edge appears twice, once in each endpoint’s list. So the list lengths (the degrees) add up to 2E. Here that’s 2 + 2 + 2 + 1 + 1 = 8 = 2 × 4.
Diagram
The same graph as an adjacency matrix and as an adjacency list:
Implementation
def to_matrix(n, edges, directed=False):
# n x n table of 0/1; matrix[u][v] == 1 means an edge u -> v exists
matrix = [[0] * n for _ in range(n)]
for u, v in edges:
matrix[u][v] = 1
if not directed:
matrix[v][u] = 1 # undirected edge {u, v} is stored in both cells
return matrix
def to_adj_list(n, edges, directed=False):
# adj[u] lists every v with an edge u -> v
# All n keys are created up front, so a vertex with no edges still
# appears (with n = 3 and no edges: {0: [], 1: [], 2: []}).
adj = {u: [] for u in range(n)}
for u, v in edges:
adj[u].append(v)
if not directed:
adj[v].append(u) # edge [0, 1] puts 1 in adj[0] and 0 in adj[1]
return adj
edges = [[0, 1], [0, 2], [1, 2], [3, 4]]
print(to_adj_list(5, edges))
# {0: [1, 2], 1: [0, 2], 2: [0, 1], 3: [4], 4: [3]}
print(to_adj_list(5, edges, directed=True))
# {0: [1, 2], 1: [2], 2: [], 3: [4], 4: []}
Building either takes O(E) after initialisation. The matrix costs O(V²) time and space to initialise. The list costs O(V + E) in total.
Recognition
- Any time the input is “n things and a list of pairs”, build an adjacency list first. That covers Course Schedule, Course Schedule II, Graph Valid Tree, Number of Connected Components In An Undirected Graph and Redundant Connection.
- A 2-D grid where cells relate to their neighbours is a graph with implicit edges. Don’t convert it to an adjacency list. Number of Islands, Max Area of Island, Walls And Gates, Rotting Oranges, Pacific Atlantic Water Flow and Surrounded Regions all work straight on the grid.
- Clone Graph hands you the adjacency list already built into node objects (
node.neighbors). - Reach for an adjacency matrix only when V is small and you need constant-time “is there an edge u → v?” checks.
Pitfalls
- Forgetting the reverse edge for undirected input. You’ll get a traversal that works from one side of the graph and not the other.
- Missing isolated vertices. If you build with a
defaultdictand never touch vertex k, thenadjhas no key k. Looping overadjinstead ofrange(n)silently skips it. That matters when you’re counting components. - Self-loops in undirected input. Edge
[0, 0]with the code above givesadj[0] == [0, 0], one append for each direction. That’s harmless for a traversal, since 0 is already marked when it sees itself. But if you readlen(adj[0])as “number of distinct neighbours”, you get 2 for a vertex whose only neighbour is itself. - Choosing the matrix for a big sparse graph. Take V = 10⁵ and E = 2 × 10⁵. The matrix has 10¹⁰ cells, and the list has 4 × 10⁵ entries.
Active Recall
-
The adjacency list above has 8 entries for 4 edges. Why? And how many would the directed version have?
-
You need to answer “is there an edge between 3 and 4?” thousands of times. What does each representation cost per query, and how would you fix the list’s cost?
-
How many connected components does the example graph have, and is the component containing vertex 0 a tree?
-
A 4 × 4 grid with no walls is a graph. How many vertices does it have, what’s the maximum degree, and why wouldn’t you build an adjacency list for it?
Answer out loud or on paper first.
Mini-task
Judgment call: none of the problems on this list exercises degree counting on its own (they all use the graph inside a traversal), so this checkpoint is included.
A town has n people labelled 1 to n. trust is a list of pairs [a, b] meaning “a trusts b”. No pair appears twice, and nobody trusts themselves. There’s a rumour that one person is the town judge. The judge trusts nobody, and everybody else trusts the judge. Return the judge’s label, or -1 if no such person exists. For example, n = 3 and trust = [[1, 3], [2, 3]] returns 3.
Before asking for help, write down: the observation, the approach, why it’s correct, the complexity.
Transfer test
You’re storing a social network with a billion users, each with about 200 friends, and the most common operation is “list this user’s friends”. Adjacency matrix or adjacency list? Would you use it? Why?
Matrix DFS
Foundation
Think of a paint bucket tool. You click one pixel and every same-coloured pixel connected to it changes colour, spreading until it hits a boundary. That’s depth-first search on a grid: go as deep as you can in one direction, back up when you’re blocked, try the next direction. It answers “which cells can I reach from here?”, and every time a cell is reached you can collect something from it.
Mechanics
The worked example is a 4 × 4 grid, where 0 is open and 1 is a wall:
Flood fill from (0, 0) marks every reachable open cell as 2:
dfs(r, c)first checks whether the cell is off the grid, a wall, or already marked. If any is true, return. This one guard is the base case.- Otherwise mark
grid[r][c] = 2before recursing. - Recurse into the four neighbours.
Why marking before recursing is the decision that matters: (0, 0) recurses into (0, 1), and (0, 1)’s neighbour list includes (0, 0) again. If (0, 0) were still 0 at that moment, the two cells would call each other forever. I ran a version that marks after the recursive calls on this grid and got a RecursionError. Marking first means that when (0, 1) looks back, it sees 2 and stops.
The invariant: every cell is marked at most once, and once marked it is never explored again. That’s what makes the total work proportional to the grid size.
Matrix DFS has a second classic use: counting paths from the top-left to the bottom-right. That changes one thing. A cell can sit on many different paths, so it’s marked only while it’s on the current path and unmarked on the way back out. That’s the backtracking pattern. Flood fill asks “is this cell reachable?”, which has one answer per cell. Path counting asks “how many routes are there?”, where a cell can be reused by different routes.
Diagram
The order flood fill discovers cells from (0, 0), with directions tried as down, up, right, left:
Follow the numbers. It goes right to (0, 1), down to (1, 1), down to (2, 1), and hits a dead end. It backs up to (1, 1), goes right to (1, 2), up to (0, 2), and hits another dead end. It backs up to (1, 2), goes right to (1, 3), then down, down, left. (3, 0) is open but boxed in by walls, so no path reaches it. The two simple paths to (3, 3) that path counting finds, 6 moves each:
Implementation
def flood_fill(grid, r, c):
"""Mark every open (0) cell reachable from (r, c) as 2. Mutates grid."""
rows, cols = len(grid), len(grid[0])
def dfs(r, c):
# One guard covers every reason to stop: off the grid, a wall (1),
# or already marked (2). Only an unmarked open cell (0) gets past it.
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 0:
return
grid[r][c] = 2 # mark BEFORE recursing: when (0, 1) looks back at (0, 0), it sees 2 and stops
dfs(r + 1, c) # down
dfs(r - 1, c) # up
dfs(r, c + 1) # right
dfs(r, c - 1) # left
dfs(r, c)
return grid
def count_paths(grid, r, c, visit):
"""Count simple paths from (r, c) to the bottom-right cell through open (0) cells."""
rows, cols = len(grid), len(grid[0])
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 1 or (r, c) in visit:
return 0
if (r, c) == (rows - 1, cols - 1):
return 1
visit.add((r, c)) # (r, c) is on the CURRENT path only
total = (count_paths(grid, r + 1, c, visit) + count_paths(grid, r - 1, c, visit)
+ count_paths(grid, r, c + 1, visit) + count_paths(grid, r, c - 1, visit))
visit.remove((r, c)) # unmark: path A and path B both pass through (1, 2)
return total
grid = [[0, 0, 0, 1],
[1, 0, 0, 0],
[1, 0, 1, 0],
[0, 1, 0, 0]]
print(count_paths(grid, 0, 0, set())) # 2
flood_fill(grid, 0, 0)
# grid is now [[2,2,2,1], [1,2,2,2], [1,2,1,2], [0,1,2,2]]; (3, 0) stays 0
Flood fill on an R × C grid takes O(R · C) time, because each cell is marked once and each marked cell checks 4 neighbours. Space is O(R · C) for the recursion stack in the worst case (a snake-shaped region). Path counting is exponential in the worst case, because it enumerates paths rather than cells.
Edge cases I ran: starting on a wall (0, 3) marks nothing. Starting on the isolated (3, 0) marks only (3, 0). A 1 × 1 grid [[0]] becomes [[2]]. For path counting, [[0]] gives 1, [[0, 1], [1, 0]] gives 0, and an open 2 × 2 gives 2.
Recognition
- Signals: a grid, and words like “connected”, “region”, “island”, “enclosed”, “reachable”, “flows to”. The question is about a whole group of cells, not the distance to one of them.
- On this list: Number of Islands, Max Area of Island, Pacific Atlantic Water Flow and Surrounded Regions all show these signals.
- Not DFS when the question is “fewest steps” or “minimum time”. DFS reaches a cell by whichever path it tries first, not the shortest one. That’s BFS, the next module.
- Flood fill (mark permanently) versus path enumeration (mark and unmark): if the answer depends on the route taken, you’re backtracking, and the cost is exponential.
Pitfalls
- Marking after recursing causes infinite recursion (the
RecursionErrorabove). - Recursion depth. An all-open 200 × 200 grid can need a call stack 40,000 frames deep, and CPython’s default limit is 1000 (recalled;
sys.getrecursionlimit()printed 1000 on my machine). Use an explicit stack (the Iterative DFS pattern from Trees) or raise the limit. - Mutating input you’re not allowed to touch. If the grid must survive, use a separate
visitedset, at the cost of O(R · C) extra space. - Bounds check order. Check
0 <= r < rowsbefore readinggrid[r][c]. Python’sgrid[-1]doesn’t crash. It quietly reads the last row. - Forgetting to unmark in path counting. I ran the version without
visit.remove, and it returns 1 instead of 2, because path A’s marks block path B.
Active Recall
-
Why must
grid[r][c] = 2happen before the four recursive calls, and not after them? -
On the example grid, what does
flood_fill(grid, 3, 0)mark? Andflood_fill(grid, 0, 3)? -
flood_fillnever unmarks, butcount_pathsdoes. What goes wrong ifcount_pathsstops unmarking? -
What are the time and space costs of flood fill on an R × C grid, and what’s the worst-case shape for space?
Answer out loud or on paper first.
Mini-task
Judgment call: Pacific Atlantic Water Flow and Surrounded Regions each need their own derivation of how to apply flood fill, beyond running one, so this checkpoint is skipped and that reasoning happens when you solve them.
Transfer test
An image editor’s “magic wand” selects every pixel connected to the clicked pixel whose colour is within a tolerance of the clicked colour. Images are up to 4000 × 3000. Would you use matrix DFS? Why?
Matrix BFS
Foundation
Drop a stone in a pond. The ripple reaches everything 1 unit away, then everything 2 units away, then 3. Breadth-first search works the same way. It visits cells in rings of equal distance from the start, so the first time it reaches any cell, it has reached it by the shortest route. It answers “what’s the fewest number of moves?” when every move costs the same.
Mechanics
Same grid, same start (0, 0), target (3, 3).
- Put the start in a queue and mark it seen.
- Process the queue one layer at a time. Read
len(q)once, pop exactly that many cells, and push their unseen open neighbours. When the layer is done,steps += 1. - When the target is popped, return
steps.
The invariant: at the start of each layer, the queue holds exactly the cells at distance steps, and every closer cell has already been popped. A cell’s neighbours are at most one further away, so everything pushed during layer k is at distance k + 1. No shorter route can turn up later, because all shorter distances were fully processed first.
Mark cells when you enqueue them, not when you pop them. A cell can be adjacent to several cells in the current layer. Marking on push means it enters the queue once. Marking on pop lets duplicates in. I counted pushes: 10 versus 11 on this grid, and 9 versus 13 on an open 3 × 3.
The multi-source variant: if there are several starting cells, push all of them at distance 0 before the loop starts. Every cell then gets the distance to its nearest source. It’s correct because it’s the same as adding one imaginary vertex joined to every source and running ordinary BFS from it. Every distance shifts by one layer, and nothing else changes, in the reasoning or in the code.
Diagram
The distance of each cell from (0, 0), which is also the layer it’s popped in:
The same grid with two sources, (0, 0) and (3, 3), seeded together at distance 0:
(1, 3) drops from 4 to 2, because (3, 3) is closer. (3, 2) drops from 7 to 1.
Implementation
from collections import deque
def shortest_path(grid, sources, target):
"""Fewest moves from any cell in `sources` to `target` through open (0) cells; -1 if unreachable."""
rows, cols = len(grid), len(grid[0])
q = deque() # (recalled: deque.popleft is O(1); list.pop(0) is O(n))
seen = set()
for r, c in sources:
if grid[r][c] == 0:
q.append((r, c))
seen.add((r, c)) # mark on ENQUEUE, so each cell is pushed at most once
steps = 0
while q:
# Invariant: q holds exactly the cells at distance `steps` from the
# nearest source. With source (0, 0): steps = 2 -> q = [(1, 1), (0, 2)].
for _ in range(len(q)): # range(len(q)) is evaluated once, so only this layer is popped
r, c = q.popleft()
if (r, c) == target:
return steps
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0 and (nr, nc) not in seen:
seen.add((nr, nc))
q.append((nr, nc))
steps += 1
return -1 # queue ran dry: target is in a different region, like (3, 0)
grid = [[0, 0, 0, 1],
[1, 0, 0, 0],
[1, 0, 1, 0],
[0, 1, 0, 0]]
print(shortest_path(grid, [(0, 0)], (3, 3))) # 6
print(shortest_path(grid, [(0, 0)], (3, 0))) # -1
print(shortest_path(grid, [(0, 0), (3, 3)], (1, 3))) # 2
print(shortest_path([[0]], [(0, 0)], (0, 0))) # 0
print(shortest_path([[1]], [(0, 0)], (0, 0))) # -1: the only source is a wall
Time O(R · C), because each cell is pushed and popped at most once and checks 4 neighbours. Space O(R · C) for seen and the queue.
Recognition
- Signals: “minimum number of steps / moves / minutes / transformations”, with every move costing the same. If the answer is a count of hops, think BFS.
- Several starting points spreading at the same time (“every X affects its neighbours each minute”, “distance to the nearest Y”) means multi-source BFS. Walls And Gates and Rotting Oranges show this signal.
- The graph doesn’t have to be a grid. Word Ladder asks for a minimum number of transformations, so it’s BFS over vertices you generate yourself.
- Not BFS when moves have different costs. That’s Dijkstra (Advanced Graphs). And not needed when you only care whether a cell is reachable, not how far it is. DFS is simpler there.
Pitfalls
- Marking on pop lets duplicates into the queue (11 versus 10 pushes here, 13 versus 9 on an open 3 × 3). The answer is still right, but the work grows. With several sources it’s also easy to count a cell twice.
- Incrementing
stepsper pop instead of per layer. Thenstepscounts cells processed, not distance. - Returning
stepsoff by one. Decide whether you count moves (start = 0) or cells on the path (start = 1), and check it against a 1 × 1 grid. Here[[0]]returns 0. - Using a list as the queue.
list.pop(0)shifts every element, so the loop turns quadratic. - A blocked source. If the start cell is a wall, return -1 before the loop, which is what the
grid[r][c] == 0check in the seeding loop does.
Active Recall
-
Why is the first time BFS pops (3, 3) guaranteed to give the shortest distance?
-
Marking on enqueue gave 10 pushes on this grid. Marking on pop gave 11. Where does the extra push come from?
-
With sources (0, 0) and (3, 3) seeded together, (3, 2) gets distance 1. What does each number in that grid mean now, and why does seeding both at distance 0 produce it?
-
What breaks if you replace the
for _ in range(len(q))loop with a plainwhile q:that pops one cell and then doessteps += 1?
Answer out loud or on paper first.
Mini-task
Judgment call: Word Ladder has to be derived from scratch, starting with what counts as a vertex and what counts as a neighbour, before any BFS runs, so this checkpoint is skipped and that derivation happens when you solve it.
Transfer test
A warehouse robot moves on a grid. Most floor tiles take 1 second to cross, but some are sticky and take 5 seconds. You want the fastest route from dock to shelf. Would you use matrix BFS? Why?
Adjacency List
Foundation
Grids come with their edges built in. Most other graphs arrive as a list of pairs, and you build the adjacency list yourself (from the first module). Then DFS and BFS work exactly as they did on grids, except “the four neighbours” becomes “adj[u]”. The new thing is direction. A directed edge u → v means “u leads to v” or “u must come before v”, and that raises a question grids never did: can following the arrows bring you back to where you started? For dependencies (“build step u must run before step v”), a loop means no valid order exists. When there’s no loop, you want an order.
Mechanics
The worked example: 6 build steps, directed edges [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [5, 4]], where u → v means “u before v”.
BFS on an adjacency list is the Matrix BFS loop with for v in adj[u] as the neighbour loop. From 0, the fewest hops to 4 is 3 (0 → 1 → 3 → 4). From 4 to 0 it’s -1, because edges only go one way.
Directed cycle detection with three colours. A plain visited set isn’t enough in a directed graph. Every vertex gets a colour:
- WHITE: not visited yet.
- GRAY: visited, and still on the current recursion path (we’re inside its
dfscall). - BLACK: finished. Every vertex reachable from it has been explored, and none of them led back.
When dfs(u) looks at a neighbour v:
- v is GRAY: v is an ancestor of u on the current path, so there’s a path v → … → u, and the edge u → v closes it into a cycle. Report the cycle.
- v is WHITE: recurse into v.
- v is BLACK: skip v. Is that safe? For u → v to be part of a cycle, v would need a path back to u. If it had one, v’s own DFS would have walked that path. It would either have met u as GRAY and reported the cycle, or found u WHITE, visited it, and finished it, in which case u would already be BLACK and could not be GRAY now. Neither happened, so the path doesn’t exist.
The BLACK case is why two colours aren’t enough. In the example, 0 → 1 → 3 and 0 → 2 → 3 both reach 3 (a diamond). When dfs(2) looks at 3, 3 has already been visited through 1, but that’s two routes to the same place, not a loop. I ran a visited-only version on this DAG and it wrongly reports a cycle.
Ordering for free. Record each vertex when it turns BLACK (postorder). Then reverse the list. For every edge u → v, u comes before v. Why: when dfs(u) examines v, either v is WHITE (so it recurses and v finishes first), or v is already BLACK (already finished). GRAY would be a cycle. Either way v finishes before u, so v is earlier in the postorder and later in the reversed list.
Finally, loop over every vertex and start a DFS from each one still WHITE. The graph may not be reachable from vertex 0 (vertex 5 isn’t).
Diagram
The trace I got from running the code on the six real edges (no dashed edge):
With the dashed edge 4 → 1 added:
Implementation
from collections import deque
WHITE, GRAY, BLACK = 0, 1, 2
def build(n, edges):
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v) # directed: u -> v only
return adj
def bfs_hops(adj, src, dst):
q, seen, steps = deque([src]), {src}, 0
while q:
for _ in range(len(q)): # one layer = every vertex exactly `steps` hops from src
u = q.popleft()
if u == dst:
return steps
for v in adj[u]:
if v not in seen:
seen.add(v)
q.append(v)
steps += 1
return -1
def cycle_or_order(n, adj):
"""Return (True, []) if a directed cycle exists, else (False, order) with u before v for every edge u -> v."""
color = [WHITE] * n
post = []
def dfs(u):
color[u] = GRAY # u is on the current recursion path
for v in adj[u]:
if color[v] == GRAY:
return True # v is an ancestor of u still on the path: edge u -> v closes a loop (4 -> 1 above)
if color[v] == WHITE and dfs(v):
return True
# color[v] == BLACK: v already finished without reaching a GRAY vertex,
# so edge u -> v can't be part of a cycle (edge 2 -> 3 above)
color[u] = BLACK # every path out of u explored, none looped back
post.append(u) # v finished before u for every edge u -> v
return False
for u in range(n): # vertices 0..n-1: vertex 5 is not reachable from 0, so this loop is what finds it
if color[u] == WHITE and dfs(u):
return True, []
return False, post[::-1]
edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [5, 4]]
adj = build(6, edges)
print(bfs_hops(adj, 0, 4), bfs_hops(adj, 4, 0)) # 3 -1
print(cycle_or_order(6, adj)) # (False, [5, 0, 2, 1, 3, 4])
print(cycle_or_order(6, build(6, edges + [[4, 1]]))) # (True, [])
Edge cases I ran: a single vertex with no edges gives (False, [0]). A self-loop [[0]] gives (True, []), since 0 is GRAY when it sees itself. Three isolated vertices give (False, [2, 1, 0]), which is valid because there are no edges to violate. 0 → 1, 1 → 0 gives (True, []).
Time O(V + E): each vertex goes WHITE → GRAY → BLACK once, and each edge is examined once from its source. Space O(V) for colours and the recursion stack, plus the O(V + E) adjacency list.
Recognition
- Signals: “n items and a list of pairs”, “dependencies”, “prerequisites”, “must happen before”, “is it possible to finish”, “return an order”. Course Schedule and Course Schedule II show the directed cycle / ordering signals. Number of Connected Components In An Undirected Graph and Graph Valid Tree show explicit-edge, undirected signals.
- Clone Graph gives you the adjacency list as objects. The
seenstructure can be a dict that maps each vertex to something you’ve built for it, not just a set. - Three colours are for directed graphs. For undirected graphs, “have I seen this vertex, and is it not the vertex I just came from?” detects a cycle, and so does Union-Find (next module).
- Kahn’s algorithm (repeatedly remove vertices with in-degree 0) is the BFS way to get the same ordering. It’s taught with Topological Sort in Advanced Graphs.
Pitfalls
- Two colours in a directed graph give false cycles on diamonds (the visited-only version I ran says “cycle” on this DAG).
- Three colours on an undirected graph. Edge {0, 1} is stored as 0 → 1 and 1 → 0.
dfs(1)sees 0 as GRAY and reports a cycle on a single edge (I ran it, and it did). For undirected graphs, pass the parent and skip it. - Edge direction backwards. “[a, b] means b before a” is common in problem statements. Getting it backwards still finds cycles correctly but produces the order reversed. Check against one pair by hand.
- Starting only from vertex 0. Unreachable vertices never get coloured, so they’re missing from the order and their cycles go undetected.
- Forgetting to return early once a cycle is found. The order then contains partial garbage.
- Recursion depth. A dependency chain of 10⁴ vertices exceeds the default recursion limit of 1000 (recalled).
Active Recall
-
bfs_hops(adj, 0, 4)is 3, butbfs_hops(adj, 4, 0)is -1. Why doesn’t reachability go both ways here, when it did in the Intro example? -
When
dfs(2)examines 3, 3 is BLACK. Why is skipping it safe, and what would a visited-only check have done? -
Show that the reversed postorder
[5, 0, 2, 1, 3, 4]has u before v for the edges 2 → 3 and 5 → 4, and explain why that holds for every edge. -
With edge 4 → 1 added, which vertices are GRAY at the moment the cycle is detected, and which of them are on the cycle?
Answer out loud or on paper first.
Mini-task
Judgment call: Course Schedule and Course Schedule II require modelling the input as a directed graph and working out what the answer means in graph terms on your own, so this checkpoint is skipped and that happens when you solve them.
Transfer test
A spreadsheet recalculates when a cell changes. Each cell’s formula may reference other cells, and circular references must be reported as errors. Would you use the adjacency-list DFS with three colours? Why?
Union-Find
The problems below also need this. Redundant Connection, Graph Valid Tree and Number of Connected Components In An Undirected Graph all ask undirected connectivity questions while edges arrive one at a time, and Union-Find answers those in near-constant time per edge.
Foundation
Picture companies merging. Every company has one CEO at the top. To ask “do these two employees work for the same company?”, each walks up the reporting chain to their CEO, and you compare CEOs. When two companies merge, one CEO starts reporting to the other, and the whole company comes along in one move. Union-Find (a disjoint set union, or DSU) is exactly that. It keeps a set of groups that only ever merge, and answers “same group?” fast.
Mechanics
State: parent[x] for each vertex. A vertex with parent[x] == x is a root, the group’s representative.
- find(x): follow
parentuntil you reach a root. That root names x’s group. Path compression: after finding the root, point every vertex on the path directly at it, so the next find is one hop. - union(a, b): find both roots. If they’re equal, a and b are already connected, so return False. Otherwise attach one root under the other and return True. Union by size: attach the smaller tree under the larger, so trees stay shallow.
Why union by size keeps trees shallow: a vertex gets one level deeper only when its tree is attached under a tree at least as big, which at least doubles the size of the tree it belongs to. That can happen at most log₂ n times, so depth stays at or below log₂ n. With path compression added, the amortised cost per operation is O(α(n)), where α is the inverse Ackermann function, below 5 for any practical n (recalled, not derived here).
Invariant: two vertices have the same root if and only if the edges processed so far connect them. A union that returns False means the edge joins two vertices that were already connected. In an undirected graph, that edge closes a cycle.
The worked example: n = 6, edges processed in order (0, 1), (2, 3), (1, 2), (4, 5), (0, 3).
Diagram
The states I got from running the code below:
The forest before and after the last find:
Implementation
class DSU:
def __init__(self, n):
self.parent = list(range(n)) # every vertex 0..n-1 starts as its own root
self.size = [1] * n # size[r] is only meaningful while r is a root
self.components = n
def find(self, x):
root = x
while self.parent[root] != root: # climb until a vertex is its own parent
root = self.parent[root]
while self.parent[x] != root: # path compression: point every vertex on the path at root
self.parent[x], x = root, self.parent[x] # find(3): parent[3] 2 -> 0, then x = 2, whose parent is already 0
return root
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # union(0, 3): find(0) == find(3) == 0, so edge (0, 3) adds no new connection
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra # union by size: rb is now the root of the smaller (or equal) tree
self.parent[rb] = ra # union(1, 2): ra = 0, rb = 2, both size 2, so 2 goes under 0
self.size[ra] += self.size[rb]
self.components -= 1 # two separate groups became one
return True
d = DSU(6)
for a, b in [(0, 1), (2, 3), (1, 2), (4, 5), (0, 3)]:
print(a, b, d.union(a, b))
print(d.parent, d.components) # [0, 0, 0, 0, 4, 4] 2
Edge cases I ran: DSU(1).union(0, 0) returns False with 1 component. On DSU(3), union(0, 1) returns True, then union(1, 0) returns False, leaving 2 components.
Time: O(α(n)) amortised per find/union (recalled), so O(n + E · α(n)) for n vertices and E edges. Space O(n).
Recognition
- Signals: undirected connectivity; edges arriving one at a time, or all at once in no useful order; “are these connected”, “how many groups”, “which edge first created a cycle”; merges only, never splits. Redundant Connection, Graph Valid Tree and Number of Connected Components In An Undirected Graph show these signals.
- Versus DFS/BFS: both answer connectivity. A traversal needs the whole graph up front and gives you paths and distances. Union-Find handles edges one at a time, needs no adjacency list, but can’t tell you a path or a distance.
- Not for directed graphs. Union-Find forgets direction. Edges 0 → 1, 1 → 2, 0 → 2 contain no directed cycle, but
union(0, 2)returns False. - Not when edges get deleted. There’s no cheap “split”.
Pitfalls
- Comparing
parent[a] == parent[b]instead offind(a) == find(b). Afterunion(1, 2)above,parent[3] == 2andparent[1] == 0, but 1 and 3 are connected. - Attaching a vertex instead of a root.
parent[a] = bwithout finding roots first can cut a out of its existing group. - Skipping both optimisations. Unioning a chain naively (0 under 1, 1 under 2, …) gave me
parent = [1, 2, 3, 4, 4], a path of height 4. Finds degrade to O(n) each. - 1-indexed input. If vertices are labelled 1..n, allocate
n + 1slots, or subtract 1 everywhere. - Counting components with a separate pass over
parentinstead of overfind(i). A non-root’sparententry isn’t its group’s name.
Active Recall
-
After
union(1, 2),parent = [0, 0, 0, 2, 4, 5]. What doesfind(3)do, step by step, and what doesparentlook like afterwards? -
union(0, 3)returned False. What does that say about the graph built from these five edges? -
Without union by size and path compression, unioning 0-1, 1-2, 2-3, 3-4 produced
parent = [1, 2, 3, 4, 4]. What doesfind(0)cost, and how does union by size prevent that shape? -
Why can’t Union-Find replace three-colour DFS for directed cycle detection?
Answer out loud or on paper first.
Mini-task
Judgment call: every list problem here that uses Union-Find hands you explicit edges to union. None of them makes you notice that a relation in the input behaves like connectivity, so this checkpoint is included.
You’re given equations over single lowercase letters, each either "x==y" or "x!=y" (always 4 characters). Return True if you can assign an integer to every letter so that all equations hold at the same time. For example, ["a==b", "b!=c", "c==a"] returns False, and ["a==b", "b==c", "a==c"] returns True.
Before asking for help, write down: the observation, the approach, why it’s correct, the complexity.
Transfer test
A network monitoring tool tracks which servers can reach each other. Cables get plugged in and unplugged all day, and operators constantly ask “can server A reach server B right now?”. Would you use Union-Find? Why?
Integration
Every problem in this topic reduces to a traversal over some graph, with a choice about what “visited” means.
- Intro to Graphs decides the shape. A grid means neighbours are computed. Pairs mean you build an adjacency list. Node objects mean the list is already built.
- Matrix DFS and the DFS half of Adjacency List answer “what can I reach?” with a permanent visited mark. Matrix BFS answers “how few steps?” with the same mark set at enqueue time, processed layer by layer, and seeded from one source or many.
- Three colours extend “visited” to “visited and still on my path”, which is what directed cycles and dependency orders need.
- Union-Find answers undirected connectivity without traversing at all, one edge at a time.
Distinguishing competing approaches:
| The question | Reach for | Not |
|---|---|---|
| Which cells/vertices are connected to this one? | DFS (or BFS, same set) | Union-Find unless edges stream in |
| Fewest moves, all moves equal cost | BFS, layer by layer | DFS (first path found isn’t the shortest) |
| Nearest of several sources, for every cell | Multi-source BFS, all sources at distance 0 | One BFS per source |
| Can these dependencies be satisfied? Give an order | Three-colour DFS + reversed postorder | Visited-only DFS (false cycles) |
| Does this undirected edge close a cycle? How many groups? | Union-Find, or DFS with a parent check | Three colours (flags every edge) |
| Moves cost different amounts | Dijkstra (Advanced Graphs) | BFS |
A recognition checklist for an unfamiliar problem:
- What are the vertices and what are the edges? If the statement doesn’t say, what changes one state into another?
- Directed or undirected? Does a pair
[a, b]mean “a before b” or “b before a”? - What’s the question: reachability, count of groups, minimum steps, an order, or a cycle?
- Minimum steps with equal costs means BFS. Everything else starts as DFS unless edges stream in, which means Union-Find.
- What does “visited” mean here: permanent, only on the current path (backtracking), or GRAY/BLACK?
- When is a vertex marked (before recursing, on enqueue), and what prevents an infinite loop?
- Is every component covered? Do you need an outer loop over all vertices or cells?
- What’s the recursion depth? Past about 1000, go iterative.
The problems
Work them with the solving cycle from Part 1: a 15-minute struggle, the key sentence, spaced repetition. For graphs, spend the struggle this way. Sketch a small example first. Decide whether it’s DFS, BFS, Dijkstra or a topological sort, and whether you need cycle detection or just a visited set. Simulate by hand before coding. Then explain the traversal order and exactly how your code avoids infinite loops.
13 problems · 0 easy · 12 medium · 1 hard · tracker spreadsheet (.xlsx)
| # | Problem | Difficulty | Coach |
|---|---|---|---|
| 1 | Number of Islands | Medium | ChatGPT · Claude |
| 2 | Max Area of Island | Medium | ChatGPT · Claude |
| 3 | Clone Graph | Medium | ChatGPT · Claude |
| 4 | Walls And Gates | Medium | ChatGPT · Claude |
| 5 | Rotting Oranges | Medium | ChatGPT · Claude |
| 6 | Pacific Atlantic Water Flow | Medium | ChatGPT · Claude |
| 7 | Surrounded Regions | Medium | ChatGPT · Claude |
| 8 | Course Schedule | Medium | ChatGPT · Claude |
| 9 | Course Schedule II | Medium | ChatGPT · Claude |
| 10 | Graph Valid Tree | Medium | ChatGPT · Claude |
| 11 | Number of Connected Components In An Undirected Graph | Medium | ChatGPT · Claude |
| 12 | Redundant Connection | Medium | ChatGPT · Claude |
| 13 | Word Ladder | Hard | ChatGPT · Claude |
Take this lesson as a live session
If you’d rather be taught this interactively, with the coach waiting for your answers, open the full lesson prompt in a chat (it covers the four prerequisites, so ask for Union-Find at the end if you want that too).