Graphs I — Representation & DFS

Review boundary and corrected contracts

Mark a vertex when its expansion starts. Graph cloning must register original→clone before following neighbors, including self-loops. Island sinking intentionally mutates the grid and can exceed Python recursion depth on large connected regions; use an explicit stack there.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Where the theory lives

If the underlying data structure feels shaky, the from-scratch explanation for graphs is in the 6-month plan: S030 — theory.

Learning objective: Represent any graph as an adjacency list in three lines, run DFS with a visited set without ever infinite-looping, and see grids as graphs so island problems become mechanical.

Series: LeetCode — From Basics to Production-Ready · Session 27 / 65 · Phase 1 · Core patterns

Watch first

Optional original references: Number of Islands, graph DFS, and DFS versus BFS. The representations and traces below are self-contained.

Why this session exists

Grids are graphs. That single sentence collapses an entire category of problems that otherwise look like a separate topic. For island counting, vertices are the land cells and edges join orthogonally adjacent land pairs; water cells are excluded rather than counted as isolated components. Once you internalise that, "Number of Islands" stops being a grid puzzle and becomes "count connected components", which you already know how to do.

The reason people struggle with graph problems is not the traversal. DFS is six lines. The struggle is representation: given a problem statement that mentions courses, or friends, or cities, or a matrix, what is the node and what is the edge? Answer that correctly and the rest of the session is typing. Answer it wrong and no amount of algorithmic cleverness saves you.

This session is deliberately narrow. One representation (adjacency list), one traversal (DFS), one bookkeeping structure (visited set). Sessions 28 through 30 add BFS, topological order and union-find on top of exactly this foundation, so getting the base solid now pays four times.

Blank-file warm-up

Five minutes, empty file, no notes. Write from memory:

adj = defaultdict(list)   — build it from an edge list
dfs(node)                 — recursive, with a visited set

Specifically: given edges = [[0,1],[1,2],[3,4]] and n = 5, build the adjacency list for an undirected graph, then write a DFS that visits every node reachable from 0 and prints them.

The two things that go wrong from memory: forgetting that undirected means you append the edge in both directions, and marking a node visited at the wrong moment. If either of those wobbles, that is today's finding.

Pattern anatomy

The shape of problem that summons this pattern: things connected to other things, and a question about reachability or grouping. Not ordering (that is session 29), not shortest distance (that is session 28) — just "what can I reach" or "how many separate clumps are there".

The invariant DFS maintains is exactly one sentence: every node in visited has already had its own expansion started, so it never needs to be expanded again. That is what makes the traversal terminate on cyclic graphs. Drop the invariant and a triangle graph loops forever.

The adjacency list uses integer vertex labels in range(n) and valid endpoint pairs. Isolated vertices need not appear as keys: defaultdict(list) supplies an empty neighbor list on access, and the component sweep still visits all n labels. count_components is for undirected graphs; directed strongly connected components need a different algorithm.

from collections import defaultdict
 
def build(n, edges, directed=False):
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        if not directed:
            adj[v].append(u)
    return adj

The DFS template. Learn this exact shape:

def dfs(node, adj, visited):
    visited.add(node)              # mark on ENTRY, not on exit
    for nxt in adj[node]:
        if nxt not in visited:
            dfs(nxt, adj, visited)

Counting connected components is then a single sweep over all nodes:

def count_components(n, edges):
    adj = build(n, edges)
    visited = set()
    count = 0
    for node in range(n):
        if node not in visited:
            dfs(node, adj, visited)
            count += 1             # each fresh start = one new component
    return count

The grid helper below assumes a nonempty rectangular grid and an in-bounds, unseen land starting cell. Its adjacency list is implicit: compute neighbors on the fly. It does not validate its starting cell.

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
 
def grid_dfs(grid, r, c, seen):
    R, C = len(grid), len(grid[0])
    seen.add((r, c))
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in seen and grid[nr][nc] == "1":
            grid_dfs(grid, nr, nc, seen)

That bounds check — 0 <= nr < R and 0 <= nc < C — must come before the grid lookup in the same and chain. Python short-circuits left to right, so ordering it correctly is what prevents an index error rather than an explicit try block.

The cue

You are looking at a graph-DFS problem when the statement contains one of these tells:

1. A 2D grid plus a notion of adjacency. Islands, regions, provinces, flood fill, surrounded areas, rotting fruit. The word "adjacent" or "connected horizontally or vertically" is the giveaway. Cells are nodes; the four (or eight) directions are edges.
2. "How many groups / islands / provinces / friend circles" — that is literally counting connected components. Outer loop over all nodes, inner DFS, increment on each fresh start.
3. An explicit edge list or n nodes numbered 0 to n−1. LeetCode hands you edges = [[a,b],...]. Build the adjacency list immediately, before you think about anything else.
4. "Can you reach X from Y" / "is everything connected". Pure reachability. Run one DFS from a source and compare len(visited) against n.
5. A structure with pointers and possible cycles — Clone Graph, copying a linked structure. The visited map does double duty: cycle guard and old-node-to-new-node mapping.

The negative cue matters too. If the problem asks for the shortest path in an unweighted graph, DFS is the wrong tool — use BFS (session 28). DFS finds a path, not the shortest one. If it asks for an order respecting dependencies, that is topological sort (session 29).

Guided solve

Number of Islands. Given an m × n grid of "1" (land) and "0" (water), count the number of islands, where an island is land connected horizontally or vertically.

Start by naming the graph out loud, because this is the step reviewers are actually grading. Nodes: every cell containing "1". Edges: between orthogonally adjacent land cells. Question: number of connected components. That translation is the whole problem — everything after it is the template you already wrote.

The algorithm: sweep every cell. When you find an unvisited "1", you have discovered a new island, so increment the counter and then run a DFS that consumes the entire island so you never count any of its cells again.

def numIslands(grid):
    if not grid:
        return 0
    R, C = len(grid), len(grid[0])
    count = 0
 
    def sink(r, c):
        if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] != "1":
            return
        grid[r][c] = "0"                 # mark visited by mutating the grid
        sink(r + 1, c)
        sink(r - 1, c)
        sink(r, c + 1)
        sink(r, c - 1)
 
    for r in range(R):
        for c in range(C):
            if grid[r][c] == "1":
                count += 1
                sink(r, c)
    return count

Two decisions worth defending aloud.

Mutating the grid instead of keeping a visited set. Sinking land avoids the separate O(m·n) visited set, but the recursive call stack can still hold O(m·n) frames. Total worst-case auxiliary space remains O(m·n), not O(1), and the caller's mutable rectangular grid is destroyed. A visited set preserves the grid at the same asymptotic time and space costs.

Guard-at-the-top recursion instead of guard-before-the-call. Both work. Guarding inside sink means one bounds check written once, at the cost of some no-op recursive calls. Guarding before each call avoids those frames but repeats the condition four times. I prefer the top guard because it is shorter and there is exactly one place for a bounds bug to live.

Trace it mentally on the single-row grid [["1","1","0","1"]]. The sweep hits (0,0), counts island 1, sinks (0,0) and (0,1). It skips (0,2) which is water. It hits (0,3), counts island 2, sinks it. Answer 2. Correct.

Recursion depth is a real input constraint: this neighbor order can snake through all 90,000 cells of a 300×300 all-land grid. The configured limit is available from sys.getrecursionlimit(); it is not a promise that all valid problem inputs fit. Keep the recursive version for bounded-depth teaching examples and use an explicit stack when a long component is possible.

Here is the same in-place algorithm without recursive frames. Mark on push so each land cell is scheduled once; marking on pop can also work, but requires skipping already-processed duplicates before expansion.

def numIslands_iterative(grid):
    if not grid or not grid[0]:
        return 0
    R, C = len(grid), len(grid[0])
    count = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] != "1":
                continue
            count += 1
            grid[r][c] = "0"
            stack = [(r, c)]
            while stack:
                i, j = stack.pop()
                for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    ni, nj = i + di, j + dj
                    if 0 <= ni < R and 0 <= nj < C and grid[ni][nj] == "1":
                        grid[ni][nj] = "0"
                        stack.append((ni, nj))
    return count

It still uses O(m·n) worst-case stack space and mutates the input. On [["1","1","0","1"]] both versions return 2 and leave only water.

Solo timed

Fifteen minutes each, timer visible, no editorial until it fires.

• Clone Graph — the visited structure is a dict, not a set, and it maps original node to its clone. Create the clone before you recurse into neighbours, or a cycle sends you into infinite recursion.
• Max Area of Island — same sweep as Number of Islands, but the DFS returns a number instead of nothing. Think about what the base case should return and what you accumulate from the four recursive calls.

If both land early, do Flood Fill as a third. Use the starting color as the eligibility predicate and return immediately when the new color equals it; otherwise recoloring is the visited mark. For Max Area, return 0 on water or out-of-bounds and otherwise mark the cell and return 1 plus the four recursive areas, taking a maximum over fresh outer starts.

Common failure modes

Marking visited on exit instead of on entry. If you add the node to visited after the neighbour loop, a cycle re-enters the node before the mark lands and you recurse forever. Mark first line of the function, always.

Forgetting the reverse edge in an undirected graph. adj[u].append(v) without adj[v].append(u) silently makes the graph directed. Traversal still runs and still returns an answer — just the wrong one. This is the most expensive one-line bug in graph problems because there is no crash to point at it.

Bounds check ordering in grids. Writing if grid[nr][nc] == "1" and 0 <= nr < R throws before the guard runs. Negative indices are worse: grid[-1][0] is a valid Python expression that silently reads the last row, so you get wrong answers with no exception at all.

Counting components inside the DFS instead of outside. The increment belongs in the outer sweep, once per fresh start. Incrementing per visited node counts cells, not islands.

Using a plain dict where defaultdict(list) was intended. adj[u].append(v) raises KeyError on a node with no prior entry. Isolated nodes are a real test case.

Myth: A grid problem and a graph problem are different topics, so I need a separate technique for each.

Why: A grid is just a graph with an implicit adjacency function. The only difference is that you never materialise the adjacency list — you compute neighbours arithmetically from (r, c) and the direction vectors. Every graph algorithm you learn transfers unchanged: DFS, BFS, union-find, even Dijkstra on a weighted grid. Treating them as separate topics doubles what you have to memorise and hides the fact that 'count islands' and 'count friend circles' are the same problem in different clothes.

Steps 1: Because a graph traversal must not revisit a node, some record of visited nodes is mandatory — otherwise a cycle produces non-termination.

Steps 2: A hash set supports expected O(1) membership and amortized expected O(1) insertion under ordinary hashing assumptions; a boolean array also works for dense integer vertex labels.

Steps 3: Because DFS marks on entry, every node is added exactly once and every edge is examined at most twice in an undirected graph.

Steps 4: Because each fresh outer-loop start reaches exactly one maximal connected set, the number of fresh starts equals the number of connected components.

Steps 5: Therefore the whole traversal is O(V + E) — and the testable prediction is that on a fully-land grid of m×n cells, the DFS visits exactly m·n cells and the outer sweep triggers exactly one fresh start, so the reported island count is 1 regardless of grid dimensions.

Picture: You are pouring water onto a cell. It spreads to every reachable neighbour and stops at the boundary of the shape. When the flow stops, one whole component has been consumed. You then walk to the next dry spot and pour again.

Trigger: Fires whenever a problem says 'connected', 'adjacent', 'region', 'group', or 'island' — and asks how many, or how big, rather than how far.

Name: Recursive DFS

Gain: Shortest to write, reads exactly like the definition, no explicit stack bookkeeping

Cost: Stack depth follows the current DFS-tree path, not necessarily the graph's longest simple path; it can reach O(V) and exceed the configured recursion limit

Name: Iterative DFS with explicit stack

Gain: Avoids recursive-call limits; capacity still depends on available memory and O(V + E) representation costs

Cost: Ten lines instead of six; easy to mark visited at the wrong moment (on push vs on pop) and double-process nodes

Name: Mutate the input as the visited marker

Gain: O(1) visited-marker storage beyond the grid, but the traversal stack still needs O(V) in the worst case

Cost: Destroys the caller's data; not an option when the grid is read-only or needed afterwards

Pick: Use recursion only when the maximum DFS depth is comfortably below the runtime's remaining call budget. Prefer the explicit stack when constraints permit a long chain; vertex count or a typical sample alone does not establish safety.

Worked variant — Clone Graph, where visited stops being a set

Island counting needs only membership; cloning additionally needs the exact clone object for each original. Assume identity-hashable Node objects whose constructor Node(value) creates a fresh empty neighbors list. Registering before recursion preserves cycles, repeated references, and self-loops.

def clone_graph(node):
    """Deep-copy an undirected connected graph. LC 133."""
    if not node:
        return None
 
    # The 'visited' structure is a MAP, not a set: original -> clone.
    # It answers 'have I seen this?' AND 'what did I build for it?'.
    # A set answers only the first, which is why a set cannot work here.
    old_to_new = {}
 
    def dfs(cur):
        if cur in old_to_new:
            return old_to_new[cur]     # already cloned; return the SAME object
 
        copy = Node(cur.val)
        old_to_new[cur] = copy         # register BEFORE recursing.
                                       # Do it after and a cycle re-enters
                                       # this node, finds nothing, and
                                       # recurses forever.
 
        for nei in cur.neighbors:
            copy.neighbors.append(dfs(nei))
        return copy
 
    return dfs(node)

Two things to extract and carry forward.

Register before you recurse. This is the general form of "mark visited on entry, not on exit". In island counting you sink the cell to '0' the moment you arrive; here you insert into the map the moment you create the clone. Both block re-entry. Even a single undirected edge is stored in both directions, so delaying registration can recurse back to the parent before any clone is recorded; failure is not restricted to graphs with an undirected cycle.

Visited is whatever answers "have I processed this node, and what did I conclude?" A set is the degenerate case where the conclusion is nothing. When the conclusion is a value — a clone, a colour, a component id, a memoised cost — the same slot becomes a dict. Recognising that the set is a special case of the dict is what makes graph memoisation feel like the same pattern rather than a new one, and it is exactly the bridge into the DP module.

The complexity is unchanged: O(V + E), because each node is cloned once and each edge is walked once from each endpoint.

Memory hook — "nodes, edges, mark on entry"

Three beats, in order, and the order matters because it is the order you should think in when a graph problem appears:

• Nodes — name the node out loud before writing anything. A course. A cell (r, c). A word in the dictionary. A state (position, keys_held). If you cannot say what one node is in a short phrase, you have not modelled the problem yet, and any code you write is guessing.
• Edges — name the relation and its direction. "Prerequisite points to dependent." "Cell to its four orthogonal neighbours." Direction is the detail people skip; undirected means you insert into both adjacency lists, and forgetting the second insert produces a graph that is quietly half missing.
• Mark on entry — add to visited when you arrive, never when you leave. On entry the mark blocks re-entry and terminates cycles. On exit it does nothing until it is too late.

For the grid case the sub-peg is "in bounds, is land, not seen" — the three guards of every grid DFS, in that order. Order matters: bounds must be checked before you index, or you get an IndexError from the very guard meant to prevent it. Python's negative indexing makes r == -1 silently wrap to the last row instead of failing loudly, which is why the bounds check must be explicit rather than relying on an exception.

What reviewers actually ask

Graph representation is the highest-leverage topic in the whole rotation, because the traversal is short and the modelling is where candidates separate.

• 200 · Number of Islands (Medium) — Practice selection. Probing whether you see the grid as a graph. Follow-up: "the grid is too large for the recursion depth" — convert to an explicit stack, or use BFS.
• 133 · Clone Graph (Medium) — Practice selection. Probing the visited-as-map insight above. Follow-up: "what if the graph is disconnected?" — you need an outer loop over all nodes.
• 695 · Max Area of Island (Medium) — Practice selection. Probing whether your DFS can return a value rather than only mutate. Follow-up: return the shape rather than the size, which is 694.
• 547 · Number of Provinces (Medium) — Practice selection. Probing adjacency matrix input rather than an edge list — same algorithm, different neighbour lookup.
• 417 · Pacific Atlantic Water Flow (Medium) — Practice selection. Probing the reversal trick: do not simulate flow from every cell, run DFS inward from each ocean's border and intersect.
• 130 · Surrounded Regions (Medium) — Practice selection. Probing the same inversion — mark what touches the border as safe, flip the rest.
• 207 · Course Schedule (Medium) — Practice selection. Probing cycle detection in a directed graph, where a single visited set is insufficient and you need three states. That is L29, but it is the follow-up they reach for from here.

The escalation to watch: "is there a cycle?" on a directed graph. The undirected trick of skipping the parent does not transfer, and answering as if it does is the most common way this topic goes wrong.

Complexity

Time: O(V + E). Every node is added to visited exactly once, and once marked it is never expanded again. Each edge is examined once from each endpoint in an undirected graph, so 2E edge inspections total, which is O(E). For a grid, V = m·n and E is at most 4·m·n (each cell has at most four neighbours), so the whole thing collapses to O(m·n) — linear in the number of cells, which is the best possible since you must at least read every cell to know whether it is land.

Space: O(V). The visited set holds up to V entries. The recursion stack adds up to O(V) in the worst case — a snake-shaped island of m·n cells produces a chain of m·n frames. If you sink the grid in place you drop the set but keep the stack, so worst-case space stays O(V); the win is a constant factor, not an asymptotic one.

Self-check (answer follows each question).

Q: Why must a node be marked visited on entry to the DFS rather than after its neighbour loop finishes?

A: Because a cycle would re-enter the node before the mark is written, causing infinite recursion. Marking on entry guarantees each node begins expansion at most once.

Q: You build an adjacency list with only adj\[u].append(v) for an undirected edge list. What symptom do you see?

A: The traversal follows only the stored direction. It may accidentally give the right count or overcount depending on label order: with n = 2, storing only 1 → 0 makes the sweep from 0 then 1 count two instead of one; storing only 0 → 1 happens to count one.

Q: In a grid DFS, why must the bounds check precede the grid lookup in the same and chain?

A: Python short-circuits left to right, so the bounds check prevents the lookup from ever executing out of range. Without it, a negative index silently wraps to the far side of the grid and produces wrong answers with no exception.

Q: Where does the component counter get incremented, and why not inside the DFS?

A: In the outer sweep, once per fresh unvisited start. Incrementing inside the DFS would count individual nodes rather than maximal connected sets.

Q: What is the time complexity of counting islands on an m×n grid, and why is it not O(m·n·4)?

A: O(m·n). The factor of four for direction checks is a constant and drops out of the asymptotic bound; each cell is still expanded at most once.

Q: In Clone Graph, why does the visited structure have to be a dict mapping original to clone rather than a plain set of visited originals?

A: Because when a cycle brings you back to an already-visited node you must attach the existing clone as a neighbour, not create a second copy. A set tells you it was visited but not which clone object corresponds to it, so you would lose the identity mapping and produce a wrong structure.

Stretch: true

You can now…

• Build an adjacency list from an edge list in three lines, inserting both directions when the graph is undirected.

• Name the node and the edge of a problem in one sentence each before writing any traversal code.

• Write recursive DFS with a visited set from a blank file and explain why the mark happens on entry.

• Treat a grid as a graph: cell as node, four orthogonal neighbours as edges, and apply the in-bounds / is-land / not-seen guard order.

• Upgrade the visited set to a visited map when the traversal must remember a conclusion per node, as in Clone Graph.

• State O(V + E) and say what V and E are for a grid — R·C cells and up to 4·R·C directed edges.

• Name the recursion-depth limit as a real failure mode on large grids and convert to an explicit stack when asked.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Number of Islands enters the queue at whatever status today's attempt earned. If the blank-file adjacency list came out directed when it should have been undirected, log the warm-up itself as failed — the queue tracks retrieval from cold memory, not eventual correctness after a hint.

• A grid is a graph. Cells are nodes, the four direction vectors are the adjacency function, and you never materialise the edge list.

• The DFS invariant is one sentence: everything in visited has already begun expansion, so it is never expanded again. That is what makes cyclic graphs terminate.

• Mark visited on entry, first line of the function. Marking on exit produces infinite recursion on any cycle.

• Undirected means both directions. adj\[u].append(v) alone is a silent wrong-answer bug with no crash to point at it.

• Counting connected components = number of fresh starts in the outer sweep, not number of nodes visited.

• O(V + E) time and O(V) auxiliary traversal space; on a grid these are O(m·n) worst-case bounds. Reading all cells establishes a time lower bound, not a matching space lower bound.

Corrective source notes

• CPython v3.14.0 recursion-limit documentation — recursion depth is configured and limited; explicit-stack traversal avoids that call-depth constraint, not memory costs. Checked 2026-10-09.

• Depth First Search - Algorithms for Competitive Programming — DFS explores a graph through recursive or explicit-stack expansion. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.