Graph (DFS / BFS / Dijkstra / Topological Sort / Union-Find)

If B requires A, draw A→B. Model objects and relationships before choosing reachability, a shortest path or a valid order. These goals need different visitation rules.

Every version in this article keeps two principles:

1. Build the graph before choosing the algorithm. Once vertices and edges are fixed, "can I get there", "fewest steps", "valid order" and "how many groups" each map to one traversal. If the graph is wrong, no amount of template practice will save you.
2. Where you dedup must match what visited means. visited has two meanings: "ever visited" (mark it and never unmark), or "on the current path" (unmark when you leave). And there are three moments to dedup: when DFS enters a vertex, when BFS generates a neighbor (that is, when it is enqueued), and when Dijkstra pops a vertex. Get one wrong and you either miss answers, get answers that are too large, or turn O(V+E) into exponential time.

The article goes in this order, and each step adds exactly one idea to the previous one:

When to Use This Pattern

The brute force starts at the source and enumerates every path. The trouble is that the same vertex is reached by many paths, and the number of paths grows exponentially with the number of vertices. Take a chain of "diamonds": each diamond has two routes a → b → d and a → c → d, and k diamonds are joined end to end:

If all you want is "can I get from start to end", processing each vertex once is enough: the first time you reach d, write it down, and whenever another route reaches d later, skip it. Every vertex is entered once and every edge is looked at once, O(V+E) in total. Graph search beats brute force because of this dedup step, and every Step below differs exactly in "where do I dedup, and what does visited mean".

Recognition Checklist

• The problem talks about "adjacent", "connected", "reachable", or moving up/down/left/right on a grid
• You can say what a vertex is and what an edge is, even if the problem never mentions a graph (indices, words, lock codes and courses can all be vertices)
• It asks for the fewest steps where every step costs the same, or for the minimum total cost where steps cost different amounts
• There are "A must come before B" dependencies, and you need to detect a cycle or produce an order
• Elements keep merging in pairs, and you are asked whether two are in the same group or how many groups there are

Before You Code

Before writing code for a graph problem, answer four questions. The first two build the graph, the last two choose the traversal, and each answer leads to the next:

1. What is a vertex? A cell (r, c), an array index, a word, a four-digit lock string, a course id. A vertex must go into a set or be used as an index, so write it as an int, a str or a tuple.
2. What is an edge? One step up/down/left/right; i can jump to i+1 .. i+nums[i]; differs by one letter; "roll until you hit a wall". Then check three things: is it directed, is it weighted, and given a vertex, how do you find its neighbors quickly.
3. What is being asked, and which traversal fits? Reachability or number of pieces: Step 1. All paths or cycle detection: Step 2. Fewest steps: Step 3. A valid order: Step 4. Weighted shortest path: Step 5. Edges arriving one by one with "same group?" queries: Step 6.
4. Where do I dedup, and what does visited mean? Once question 3 is answered, so is this one: DFS reachability marks on entry and never unmarks; path finding treats visited as "on the current path" and undoes it before returning; BFS marks when it generates a neighbor; Dijkstra marks when it pops.

Try it on LC 200 Number of Islands. In the grid, "1" is land and "0" is water. Land cells that touch up, down, left or right belong to the same island; cells that only touch diagonally do not. Return the number of islands.

For example, grid = [["1","1","0"],["0","1","0"],["0","0","1"]] → 2: the three upper-left cells (0, 0), (0, 1), (1, 1) form one island, and the bottom-right cell (2, 2) only touches (1, 1) diagonally, so it is an island of its own.

• Vertex: each cell (r, c).
• Edge: two cells that are next to each other horizontally or vertically and are both "1". No need to build an adjacency list; compute the neighbors on the spot.
• What is asked: how many connected pieces. That is reachability, so DFS.
• Dedup: when you enter a cell, change it to "0" so you never enter it again, and never change it back. Every time the outer scan meets a cell that is still "1", that is a new island.

Walk through it by hand with those four answers. The outer scan goes row by row, left to right:

(0, 1) and (1, 1) were already turned into "0" before the scan reached them, so they are not counted as new islands. The LC 200 variation in Step 1 turns this into code.

Number of Islands (LeetCode 200)

Given a nonempty character grid, "1" is land and "0" water; return the island count. Only up/down/left/right adjacency connects land, not diagonals; outside the boundary is water. The DFS below marks visited by changing the input, but returns a count.

Input: grid = [["1","1","0"],["0","1","0"],["0","0","1"]]. Expected: 2.

DFS version. Neighbour order in sink: down, up, right, left. Marking a cell "0" means it has been visited.

1. Walk it by hand

2. Read the rule off the table

• The scan visits every cell once. Each time it finds a "1", that is a new island: add 1 to count, then sink it.
• sink marks the cell first, then tries all four neighbours. It stops at the grid edge, at water, and at cells already marked.
• After one sink call, the whole island is "0", so the scan never counts it again.

3. Turn each row into code

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    def sink(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
            return
        grid[r][c] = "0"
        sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1)
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                sink(r, c)
    return count

Core Templates

All six Steps use the same routine: answer the four questions, then check against the two principles at the top: is the graph right, and does the dedup moment match what visited means.

Step 1: DFS reachability, mark on entry and never unmark

Problem: n vertices and a list of undirected edges; count the connected components (LC 323).

The input is n and a list of undirected edges; vertices are numbered 0 to n − 1. Return the number of connected components. An isolated vertex with no edges is a component of its own.

For example, n = 5, edges = [[0,1],[1,2],[3,4]] → 2: {0, 1, 2} is one piece and {3, 4} another. n = 3, edges = [] → 3: three isolated vertices, one piece each.

The answer is "how many pieces", not "how many vertices one start can reach".

The four questions:

• Vertices: 0 .. n-1. Edges: the given undirected edges, stored in both directions.
• What is asked: how many pieces, which is a reachability question.
• Dedup: check and mark when entering a vertex, never unmark.

Why is unmarking unnecessary? "Which vertices can be reached from u" has nothing to do with the route that brought you to u. Once u has been reached, everything reachable from it has been, or is about to be, reached as well; entering it again is wasted work. So visited means "ever visited", and it only grows.

Why the outer loop? The graph may be disconnected, and a DFS from 0 only covers the piece that contains 0. The outer loop tries every vertex; any vertex not yet visited starts a new piece, and the count goes up by one.

First a small helper that builds the graph. Several later blocks use it:

def build_graph(n, edges):
    graph = [[] for _ in range(n)]  # n separate empty lists; not [[]] * n
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)          # undirected: add both directions
    return graph


assert build_graph(3, [(0, 1), (1, 2)]) == [[1], [0, 2], [1]]
assert build_graph(2, []) == [[], []]
assert build_graph(0, []) == []

[[] for _ in range(n)] creates a new empty list on every iteration, so each vertex gets its own adjacency list. [[]] * n looks the same but repeats one list n times: appending to graph[0] changes graph[1] and graph[2] too. _ is the usual name for a loop variable you do not use.

When vertices are not the integers 0 .. n-1 (words, coordinates, emails), swap the list for a defaultdict(list); everything else stays the same. A defaultdict(list) is a dict that, when you access a key it does not have yet, calls list() to create an empty list for it, so graph[u].append(v) works without checking whether u exists.

def count_components(n, edges):
    graph = build_graph(n, edges)
    visited = [False] * n

    def dfs(u):
        if visited[u]:              # check on entry
            return
        visited[u] = True           # mark on entry, never unmark
        for v in graph[u]:
            dfs(v)

    count = 0
    for u in range(n):              # the graph may be disconnected: try every vertex as a start
        if not visited[u]:
            dfs(u)
            count += 1
    return count


assert count_components(5, [(0, 1), (1, 2), (3, 4)]) == 2
assert count_components(5, [(0, 1), (1, 2), (2, 3), (3, 4)]) == 1
assert count_components(3, [(0, 1), (1, 2), (2, 0)]) == 1
assert count_components(3, []) == 3
assert count_components(0, []) == 0

dfs is defined inside count_components, so it can read and modify the outer graph and visited. It only changes elements of the list (visited[u] = True) and never rebinds visited itself, so no nonlocal is needed.

n = 5, edges = [(0, 1), (1, 2), (3, 4)]:

Each vertex is marked once and each edge is seen once from each end, O(V+E).

Variation: a grid is an implicit graph (LC 200)

The input is a nonempty grid grid whose cells are the strings "1" (land) or "0" (water). Return the number of islands: land cells that touch up, down, left or right belong to one island; diagonal contact does not count. Everything outside the grid is water.

For example, [["1","0"],["0","1"]] → 2: the two land cells only touch at a corner, so they are not connected.

Think first: Compared with LC 323, what are the vertices and edges now? A grid has no adjacency list, so where do a cell's neighbors come from? LC 323 uses a visited array to record "been here"; can the grid do without that array?

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    def sink(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
            return                  # out of bounds, water, or already sunk
        grid[r][c] = "0"            # mark on entry: sink it and never undo
        sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1)   # semicolons put four calls on one line
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":   # land not yet sunk: a new island
                count += 1
                sink(r, c)
    return count


assert num_islands([["1", "1", "0"], ["0", "1", "0"], ["0", "0", "1"]]) == 2
assert num_islands([["1", "0", "1"], ["0", "1", "0"], ["1", "0", "1"]]) == 5   # diagonals are not adjacent
assert num_islands([["0", "0"], ["0", "0"]]) == 0
assert num_islands([["1"]]) == 1
assert num_islands([["1", "0"], ["0", "1"]]) == 2                             # the example from the statement

Variation: search backwards from the border (LC 130)

The input is a board board of "X" and "O". A region of "O" cells connected up, down, left or right that has no cell on the border of the board is turned entirely into "X"; regions that touch the border stay. Modify the board in place; LeetCode expects no return value, and the code below returns the board only to make the asserts easy to write.

For example, in [["X","X","X"],["X","O","X"],["X","X","X"]] the middle O cannot reach the border, so it becomes X. If a path of Os reaches the border, every O connected to that path stays.

Unlike LC 200, this does not count regions; it keeps the safe regions and rewrites the rest.

Think first: Going forward means asking, for each region of O, "does it touch the border", and you only know after exploring the whole region. Can you turn it around: start Step 1's reachability from which cells so that one pass finds every safe O? Once you have them, how do you tell "safe O" apart from "O to flip"?

def solve_surrounded(board):
    if not board:
        return board
    rows, cols = len(board), len(board[0])

    def mark(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != "O":
            return
        board[r][c] = "S"           # connected to the border: safe
        mark(r + 1, c); mark(r - 1, c); mark(r, c + 1); mark(r, c - 1)

    for r in range(rows):           # left and right borders
        mark(r, 0); mark(r, cols - 1)
    for c in range(cols):           # top and bottom borders; corners are called twice, the second call returns at once
        mark(0, c); mark(rows - 1, c)
    for r in range(rows):
        for c in range(cols):
            board[r][c] = "O" if board[r][c] == "S" else "X"   # safe cells back to O; everything else (surrounded O, original X) is X
    return board


b = [list("XXXX"), list("XOOX"), list("XXOX"), list("XOXX")]
assert solve_surrounded(b) == [list("XXXX"), list("XXXX"), list("XXXX"), list("XOXX")]
assert solve_surrounded([list("OO"), list("OO")]) == [list("OO"), list("OO")]
assert solve_surrounded([]) == []
assert solve_surrounded([list("XXX"), list("XOX"), list("XXX")]) == [list("XXX"), list("XXX"), list("XXX")]   # the example from the statement

The same "walk backwards from the border" idea also solves these two:

• LC 417 Pacific Atlantic Water Flow: the input is a height matrix heights. Water flows from a cell to a neighbor (up, down, left, right) that is not higher. The top and left edges touch the Pacific, the bottom and right edges the Atlantic. Return every cell from which water can reach both oceans, in any order. For example, [[1,2],[4,3]] → [[0,1],[1,0],[1,1]].
• LC 1254 Number of Closed Islands: the input is a 0/1 grid where 0 is land and 1 is water, the opposite of LC 200. Return the number of islands that do not touch the border at all. For example, [[1,1,1],[1,0,1],[1,1,1]] → 1.

Same idea, new setting: building the graph is the whole problem (LC 399).

The input has three parts: equations[i] = [a, b] together with values[i] states one equation a / b = values[i], where every value is positive; queries is a list of divisions [c, d] to evaluate. For each query return the value of c / d, or -1.0 if it cannot be determined. The equations are guaranteed to be consistent.

For example, with a / b = 2 and b / c = 3, the queries a / c, b / a, x / x → [6.0, 0.5, -1.0]. a / c = 2 × 3; b / a is the reciprocal of a / b; x never appears in any equation, so even x / x counts as unknown.

Think first: What are the vertices and the edges? What does a / c correspond to on the graph? If there are several routes from a to c, do you need all of them? Does visited need to be undone?

from collections import defaultdict


def calc_equation(equations, values, queries):
    graph = defaultdict(dict)       # graph[a][b] = a / b; a missing key gets an empty dict
    for (a, b), v in zip(equations, values):
        graph[a][b] = v             # equation a / b = v
        graph[b][a] = 1 / v         # reverse direction uses the reciprocal

    def dfs(u, target, visited):
        if u == target:
            return 1.0
        visited.add(u)
        for v, w in graph[u].items():   # neighbor v and edge weight w
            if v not in visited:
                sub = dfs(v, target, visited)
                if sub != -1.0:
                    return w * sub  # multiply edge weights along the path
        return -1.0                 # target is not reachable from u

    res = []
    for a, b in queries:
        if a not in graph or b not in graph:
            res.append(-1.0)        # variable never seen
        else:
            res.append(dfs(a, b, set()))   # a fresh visited for each query
    return res


eq, vals = [["a", "b"], ["b", "c"]], [2.0, 3.0]
assert calc_equation(eq, vals, [["a", "c"], ["b", "a"], ["a", "e"]]) == [6.0, 0.5, -1.0]
assert calc_equation(eq, vals, [["a", "a"], ["x", "x"]]) == [1.0, -1.0]
assert calc_equation([["a", "b"], ["c", "d"]], [1.0, 1.0], [["a", "d"]]) == [-1.0]
assert calc_equation(eq, vals, [["a", "c"], ["b", "a"], ["x", "x"]]) == [6.0, 0.5, -1.0]   # the example from the statement

More of the same kind:

• LC 695 Max Area of Island: the input is a 0/1 grid with 1 as land. Return the number of cells in the largest island, or 0 if there is no land. For example, [[1,1],[0,1]] → 3.
• LC 133 Clone Graph: the input is one node of a connected undirected graph. Return the matching node in a deep copy of the whole graph. Neighbors in the copy must point to copies, never back into the original. An empty graph (input None) returns None.
• LC 1971 Find if Path Exists in Graph: the input is n, a list of undirected edges, source and destination. Return whether the two are connected. When source equals destination the answer is True (zero edges).
• LC 463 Island Perimeter: the input is a 0/1 grid with 1 as land, exactly one island and no lakes inside it. Return the island's perimeter, for example [[1,1]] → 6. The answer is the perimeter, not the area.

Step 1 recap

• What it solves: can I get there, and how many pieces are there.
• The key line: if visited[u]: return followed by visited[u] = True: check on entry, mark on entry, never unmark.
• What the variants change: LC 200 makes cells the vertices and replaces visited with "turn land into water"; LC 130 changes the starting points and walks backwards from the border; LC 399 puts weights on the edges and multiplies along the path, but visited means the same thing.
• Easiest mistake: a grid DFS that reads grid[r][c] before the bounds check. With r = -1, Python raises no error and silently reads the last row. Always put the bounds check first.

Step 1 only answers "can I get there". When the problem asks "which paths", one vertex can sit on many paths, and "mark and never unmark" stops being correct. That is Step 2.

Step 2: visited means "on the current path", undo it before returning

Problem: in a directed graph, how many paths from s to t never repeat a vertex?

The input is a directed graph as an adjacency list graph (graph[u] holds the vertices u points to), a start s and a target t. Return the number of paths from s to t in which no vertex appears twice.

For example, graph = [[1, 2], [3], [3], [4], []], s = 0, t = 4 → 2: 0→1→3→4 and 0→2→3→4. Vertex 3 is on both paths, and both are counted.

The four questions:

• Vertices and edges: the given directed graph, adjacency list graph[u].
• What is asked: all paths. The reachability template only tells you whether one exists.
• Dedup: a path may not visit a vertex twice, so what you track is "which vertices are on the current path". Add u to the path when entering it, take it out when leaving.

This is the second meaning of visited from the second principle. Whatever you did on entry, undo before returning: a vertex added to the path must be removed from it before you go back up. Otherwise, once one path has used u, no other path can ever pass through it.

def count_paths(graph, s, t):
    on_path = set()

    def dfs(u):
        if u == t:
            return 1
        if u in on_path:            # u is already on the current path; going on would loop back
            return 0
        on_path.add(u)              # entering: add to the current path
        total = sum(dfs(v) for v in graph[u])   # paths through each neighbor, added up
        on_path.remove(u)           # before returning: leave the path so other paths can use u
        return total

    return dfs(s)


assert count_paths([[1, 2], [3], [3], [4], []], 0, 4) == 2   # the example from the statement
assert count_paths([[1, 2], [2, 3], [3], []], 0, 3) == 3
assert count_paths([[1], [0, 2], []], 0, 2) == 1   # cycle between 0 and 1
assert count_paths([[1], []], 1, 0) == 0
assert count_paths([[]], 0, 0) == 1

In sum(dfs(v) for v in graph[u]), the part dfs(v) for v in graph[u] is a generator expression: it calls dfs on each neighbor in turn, and sum adds the results. It is the same as a for loop that adds into total; the calls happen one after another, so on_path contains u during all of them.

What happens if you forget on_path.remove(u). graph = [[1, 2], [3], [3], [4], []], two paths 0→1→3→4 and 0→2→3→4:

The other way round, if a Step 1 reachability problem also undoes its marks, the answer is still right, but each vertex is re-entered by different paths, and the cost grows with the number of paths. With b outgoing edges per vertex on average, the worst case is exponential, O(b^V). So before writing, ask: does the problem want "can I get there" or "which paths"?

Same idea, new setting: Word Search (LC 79).

The input is a letter grid board and a nonempty word word. Return True if you can start at some cell and, moving each time to a neighbor up, down, left or right, spell out word letter by letter without using any cell twice; otherwise return False.

For example, with [["A","B"],["C","D"]]: word = "ABD" → True (A → B → D). word = "ABA" → False: the only A next to B is the cell just used, and it cannot be reused.

The question is only "does one exist"; it does not count paths or find every word in the grid.

Think first: count_paths records "on the current path" in a set. Here the vertices are cells; can you do without the set? Which letter must recursion level i match? You can stop as soon as one path works; what must you take care of before returning early?

def exist(board, word):
    rows, cols = len(board), len(board[0])

    def dfs(r, c, i):               # can word[i:] be spelled starting at (r, c)?
        if i == len(word):
            return True             # every letter matched
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
            return False            # out of bounds, on the current path (already #), or wrong letter
        board[r][c] = "#"           # entering: mark as on the current path
        found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1)
                 or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
        board[r][c] = word[i]       # before returning: restore the letter
        return found

    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))   # try every cell as a start


board = [list("ABCE"), list("SFCS"), list("ADEE")]
assert exist(board, "ABCCED") is True
assert exist(board, "SEE") is True
assert exist(board, "ABCB") is False        # B cannot be used twice
assert exist([["a"]], "a") is True
assert exist([["A", "B"], ["C", "D"]], "ABD") is True    # the example from the statement
assert exist([["A", "B"], ["C", "D"]], "ABA") is False

Cycle detection in a directed graph (LC 207): three-color DFS.

The input is numCourses (courses 0 to n − 1) and prerequisites, where [a, b] means b must be taken before a. Return True if every course can be finished, False otherwise.

For example, n = 2, [[1, 0]] → True: take 0, then 1. [[1, 0], [0, 1]] → False: 0 and 1 are each other's prerequisite, so neither can be started.

All courses can be finished exactly when the prerequisites contain no cycle. So finding a cycle means returning False, not True.

Think first: Is the edge a → b or b → a? "Meeting yourself again on the current path" is a cycle, so count_paths' on_path can detect one; but it undoes on leaving, so the same vertex gets checked again and again. Once a vertex is fully checked and known to reach no cycle, can you record that, as in Step 1, and never enter it again? How many states does visited need then?

def can_finish(n, prerequisites):
    graph = [[] for _ in range(n)]
    for a, b in prerequisites:      # [a, b]: take b before a, edge b -> a
        graph[b].append(a)
    WHITE, GRAY, BLACK = 0, 1, 2    # assigns three names in one line
    color = [WHITE] * n

    def dfs(u):                     # True means no cycle is reachable from u
        if color[u] == GRAY:        # walked back onto the current path: cycle
            return False
        if color[u] == BLACK:       # explored before, no cycle from here
            return True
        color[u] = GRAY
        for v in graph[u]:
            if not dfs(v):
                return False
        color[u] = BLACK            # turn black when leaving, not back to white
        return True

    return all(dfs(u) for u in range(n))   # the outer loop: every vertex is a start once


assert can_finish(2, [[1, 0]]) is True                   # the example from the statement
assert can_finish(2, [[1, 0], [0, 1]]) is False
assert can_finish(3, [[1, 0], [2, 0], [1, 2]]) is True   # 1 is reached twice but there is no cycle
assert can_finish(1, [[0, 0]]) is False                  # self loop

Contrast: cycle detection in an undirected graph (LC 261 Graph Valid Tree)

The input is n (n ≥ 1, vertices 0 to n − 1) and a list of undirected edges. Return True if the edges form exactly one tree that covers every vertex, False otherwise.

For example, n = 3, [[0, 1], [1, 2]] → True. n = 3, [[0, 1]] → False: there is no cycle, but vertex 2 is not connected to anything, so it is not a tree.

Think first: Which two conditions must a tree satisfy? Apply LC 207's cycle check directly to an undirected graph: after walking from 0 to 1, 0 is among 1's neighbors and is still on the current path. What happens? How do you avoid treating "the edge you came in on" as a cycle?

def valid_tree(n, edges):
    graph = build_graph(n, edges)
    visited = [False] * n

    def has_cycle(u, parent):
        if visited[u]:              # reached a visited vertex without walking back: cycle
            return True
        visited[u] = True
        for v in graph[u]:
            if v != parent and has_cycle(v, u):   # skip the edge we came in on
                return True
        return False

    return not has_cycle(0, -1) and all(visited)   # acyclic and connected; the start has no parent, -1 fills the slot


assert valid_tree(5, [[0, 1], [0, 2], [0, 3], [1, 4]]) is True
assert valid_tree(5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]) is False
assert valid_tree(4, [[0, 1], [2, 3]]) is False    # not connected
assert valid_tree(1, []) is True
assert valid_tree(3, [[0, 1], [1, 2]]) is True     # the example from the statement
assert valid_tree(3, [[0, 1]]) is False

A different kind of path problem:

• LC 332 Reconstruct Itinerary: the input is a list of tickets, each [from, to]. An itinerary starting at "JFK" that uses every ticket exactly once is guaranteed to exist. Return the lexicographically smallest such itinerary (a list of airports). For example, [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]] → ["JFK","NRT","JFK","KUL"]: going to the smaller KUL first leaves you stuck with tickets unused. Duplicate tickets are separate edges, and airports may be revisited.

Step 2 recap

• What it solves: which paths exist, and whether there is a cycle.
• The key line: on_path.remove(u): whatever was added on entry is taken out before returning.
• What the variants change: LC 79 replaces the set with # written on the grid and restored before returning; LC 207 turns a vertex black instead of white on leaving, combining both meanings of visited; LC 261 is undirected, so it passes a parent and does not count the edge it came in on as a cycle.
• Easiest mistake: returning as soon as an answer is found and skipping the restore step (in LC 79 the board keeps some #). Store the result, restore, then return.

DFS answers "can I get there" and "which paths", but the first path it finds to the target is not necessarily the shortest. Fewest steps needs a different visiting order, which is Step 3.

Step 3: BFS expands level by level, dedup when generating

Problem : Jump Game II ( LC 45 ). nums[i] is the farthest you can jump forward from i; find the fewest jumps from 0 to the last index. (Pro lesson)

Variation: multi-source BFS (LC 994 Rotting Oranges)

The input is a grid grid where 0 is empty, 1 is a fresh orange and 2 is a rotten orange. (Pro lesson)

Variation: the edge changes, the template does not (LC 490 The Maze)

In the maze maze , 0 is open and 1 is a wall, and everything outside the maze also acts as a wall. A ball starts at start; (Pro lesson)

Step 3 recap

What it solves : the fewest steps when every step costs the same. (Pro lesson)

Step 4: topological sort, enqueue only when indegree drops to 0

Problem : Course Schedule II ( LC 210 ). n courses, [a, b] means b must be taken before a; (Pro lesson)

Variation: first read the edges out of the input (LC 269 Alien Dictionary)

An alien language uses lowercase letters, but in an unknown order. The input is a list of words already sorted by the alien alphabet. (Pro lesson)

Step 4 recap

What it solves : a valid order under dependencies; fewer than n vertices in the output means a cycle. (Pro lesson)

Step 5: Dijkstra, weighted edges, dedup on pop

Problem : Network Delay Time ( LC 743 ). A directed weighted graph; a signal is sent from k. (Pro lesson)

Variation: change the key (LC 1631 Path With Minimum Effort)

The input is a rows × cols height matrix heights. (Pro lesson)

Variation: the key is just this one edge (LC 1584, Prim)

The input is a list of distinct points in the plane. (Pro lesson)

Step 5 recap

What it solves : minimum-cost paths when edge weights are non-negative. The key line : if u in dist: continue : dedup on pop; (Pro lesson)

Step 6: Union-Find, merge instead of traversing

Problem : Redundant Connection ( LC 684 ). A tree got one extra edge and became an undirected graph with one cycle; (Pro lesson)

Step 6 recap

What it solves : as edges arrive one by one, whether two vertices are already connected and how many groups there are. (Pro lesson)

The Six Steps Together

Step Container When to dedup What visited means Answers Complexity Step 1 recursion stack on entering a vertex ever visited, never undone re… (Pro lesson)

One Problem, Many Disguises

Disguise (how the problem says it) Translated into the core problem Step LC 130 turn every O surrounded by X into X reachability from the bo… (Pro lesson)

Common Pitfalls

BFS marks visited only on pop. Before a vertex is popped, other vertices in the same level generate it again: with nums = [3, 3, 3, 3, 0] th… (Pro lesson)

Say It in the Interview

Take Course Schedule II. After confirming what [a, b] means and whether duplicate pairs can appear, you can say: I'll model each course as a… (Pro lesson)