Graph General

Graph problems are about traversal (DFS/BFS), connectivity, and ordering. The key is to pick the right representation (adjacency list, grid, or union-find) and maintain a visited invariant.

Pattern A: Flood fill (grid traversal)

Use when: you need to count or mark connected components in a grid.

Invariant: once a cell is visited, it is never processed again.

Skeleton:

for each cell:
    if cell is land and not visited:
        dfs(cell)
        count++

func dfs(r,c):
    if out of bounds or visited or water: return
    mark visited
    dfs(neighbors)

Problems:

• number-of-islands.

Pattern B: Border-connected marking

Use when: you need to keep regions connected to the border.

Invariant: only border-reachable cells are preserved.

Skeleton:

for each border cell:
    if cell == 'O': dfs mark as safe
for each cell:
    if cell == 'O': flip to 'X'
    if cell == 'S': flip back to 'O'

Problems:

• surrounded-regions.

Pattern C: Graph cloning

Use when: you must deep-copy a graph with cycles.

Invariant: every original node maps to exactly one clone.

Skeleton:

map = node->clone
func clone(node):
    if node in map: return map[node]
    copy = new Node(node.val)
    map[node] = copy
    for nei in node.neighbors:
        copy.neighbors.append(clone(nei))
    return copy

Problems:

• clone-graph.

Pattern D: Weighted edges via DFS/BFS

Use when: edges have multiplicative weights and you need any path value.

Invariant: the running product equals the path value from source to current.

Skeleton:

build adjacency with (neighbor, weight)
func search(src, dst):
    dfs(src, product=1)

Problems:

• evaluate-division.

Pattern E: Topological order / cycle detection

Use when: prerequisites create a directed graph.

Invariant: nodes are processed only after all prerequisites are satisfied.

Skeleton (DFS colors):

state: 0=unvisited, 1=visiting, 2=done
if visiting neighbor -> cycle

Skeleton (Kahn):

indegree counts
queue all 0-indegree
pop, reduce neighbors, push new 0-indegree

Problems:

• course-schedule.
• course-schedule-ii.

Pattern F: Union-Find for redundant edge

Use when: you need to find the edge that creates a cycle in an undirected graph.

Invariant: two nodes are connected if they share the same root.

Skeleton:

for edge (u,v):
    if find(u) == find(v): return edge
    union(u,v)

Problems:

• redundant-connection.

When to use Graph techniques (checklist)

• There are explicit edges or implicit neighbor rules.
• You need connectivity, reachability, or ordering.

Common failures (checklist)

• Forgetting to mark visited before recursive calls (causes cycles).
• Mixing directed and undirected graph logic.
• Not resetting visited between multiple searches.

Problem mapping

• number-of-islands: DFS flood fill.
• surrounded-regions: border marking.
• clone-graph: DFS with node map.
• evaluate-division: weighted DFS/BFS.
• course-schedule: cycle detection.
• course-schedule-ii: topological ordering.
• redundant-connection: union-find.