Modelling problems as graphs

A graph is a set of things, called nodes or vertices, together with connections between pairs of them, called edges. Modelling a problem as a graph means deciding four things: what a node is, what an edge is, whether an edge can be followed in both directions, and whether it has a cost. The question in the statement then becomes a standard question about the graph: can I get from here to there, in how few steps, which parts are connected, in what order. Stations and the track between them, grid cells and the steps between them, people and their friendships, the positions of a puzzle and the moves between them are all graphs. A few searches answer most questions about them: breadth-first search (BFS), depth-first search (DFS) and union-find in this module, then weighted shortest paths and orderings in the modules after it.

This lesson shows where a graph hides in a problem statement, how to size it before you code, how to store it as an adjacency list in Python, JavaScript, Java, C++ and Go without each language’s trap, and how the question picks the search. Then it solves one problem in full, from a brute force to an O(V + E) search in five languages: can a passenger travel between two stations of a night metro?

Where the graph hides in a problem

Problem statements rarely say “graph”. They describe things and the ways to move between them, and four kinds of description cover most coding rounds:

• Places and links, such as stations and track, computers and cables, or cities and flights. A node is a place and an edge is one link; track and cables run both ways, while a flight or a one-way street runs one way. Typical questions: can I get from A to B, and in how few hops?
• A grid, such as a maze, a map of land and water or a game board. A node is an open cell (r, c), and an edge is a step to an open neighbour, which can always be taken back. Typical questions: how many separate regions are there, and how few steps reach the exit?
• A puzzle or a machine, such as a padlock, jugs of water or a word changed one letter at a time. A node is a state, everything that decides the next move, and an edge is one move, often one way only. Typical question: how few moves reach a goal state?
• Rules between items, such as courses and prerequisites, build steps or rivals who must not sit together. A node is an item and an edge is one rule: “A before B” runs one way, “A and B clash” both ways. Typical questions: is there an order that keeps every rule, a loop that breaks them, or a split into two groups with no clash inside?

Three questions turn a description into a model.

1. What is a node? A node has to carry everything that decides which moves come next. On a grid that is the cell. In a padlock puzzle it is the whole code on the wheels, not a single wheel, because the same wheel in the same position leads to different codes when the other wheels differ. If a maze lets you knock down one wall, the cell is no longer enough: two visits to one cell differ in whether the wall is still yours to break, so the node becomes the cell together with that allowance.
2. What is an edge, and which way does it run? An edge is one allowed step. If every step can be taken back, as when a train runs both ways or a grid step is retraced, the graph is undirected, and each edge goes into the lists of both its ends. If not, as with a one-way street, a prerequisite or water poured down a drain, the graph is directed and each edge goes into one list only. When steps have different costs, such as minutes, fares or kilometres, the graph is weighted, and the route with the fewest steps may not be the cheapest one.
3. How big is it? Count the nodes V and the edges E before you write the search. Every search in this module costs O(V + E) time and O(V) memory for its marks, so the two counts tell you at once whether it fits.

Counting is quick. Here are the grid and the padlock from above, counted by generating them:

"""How big is the graph? Nodes and adjacency entries of three graphs, counted before any search is written."""

STEPS = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # up, down, left, right


def grid_entries(rows, cols):
    """Neighbour entries of an open grid, counted cell by cell."""
    return sum(1 for r in range(rows) for c in range(cols) for dr, dc in STEPS if 0 <= r + dr < rows and 0 <= c + dc < cols)


def grid_formula(rows, cols):
    """Each side-by-side pair of cells is one edge, stored in both cells' lists."""
    return 2 * (rows * (cols - 1) + (rows - 1) * cols)


# The formula agrees with counting on small grids, so it can be trusted on a big one.
assert all(grid_entries(r, c) == grid_formula(r, c) for r in range(1, 9) for c in range(1, 9))
print(f"grid 1000 x 1000: {1000 * 1000:,} nodes, {grid_formula(1000, 1000):,} entries")


def lock_moves(code):
    """A move turns one of the four wheels one step up or down; 9 turns up to 0 and 0 down to 9."""
    out = []
    for i in range(4):
        digit = int(code[i])
        for step in (1, -1):
            out.append(code[:i] + str((digit + step) % 10) + code[i + 1:])
    return out


codes = [f"{k:04d}" for k in range(10_000)]
entries = sum(len(lock_moves(code)) for code in codes)
undo = all(code in lock_moves(nxt) for code in codes for nxt in lock_moves(code))
print(f"4-wheel lock: {len(codes):,} nodes, {entries:,} entries, every move can be undone: {undo}")

grid 1000 x 1000: 1,000,000 nodes, 3,996,000 entries
4-wheel lock: 10,000 nodes, 80,000 entries, every move can be undone: True

A 1,000 × 1,000 grid has a million nodes and 3,996,000 neighbour entries. A search that touches each entry once handles that easily, while anything that compares every pair of cells, about 5 × 10¹¹ pairs, fits no time limit. The padlock has 10,000 codes and 8 moves from each, and every move can be undone by turning the same wheel back, so its graph is undirected although nobody ever draws it. Neither graph needs an adjacency list at all: the neighbours of a cell or a code can be worked out when the search asks for them, which is how grids and puzzles are nearly always searched.

A puzzle as a graph: two jugs

You have a 3-litre jug A, a 5-litre jug B, a tap and a drain, and you want exactly 4 litres in one of the jugs. Nothing in the statement mentions nodes, yet the model follows from the three questions. The next move depends only on how much water each jug holds, so a node is the pair (litres in A, litres in B). An edge is one move: fill a jug from the tap, empty one into the drain, or pour one into the other until the first is empty or the second is full.

"""The state graph of a measuring puzzle: jugs of 3 and 5 litres, a tap and a drain.

A node is a state, (litres in A, litres in B). An edge is one move. The graph is never built: moves() makes a
state's neighbours when the search asks for them.
"""

A, B = 3, 5


def moves(a, b):
    """Every state one move away from (a, b), with the move's name. Moves that change nothing are left out."""
    into_b = min(a, B - b)  # what pouring A into B can move
    into_a = min(b, A - a)
    options = [
        ("fill A", (A, b)),
        ("fill B", (a, B)),
        ("empty A", (0, b)),
        ("empty B", (a, 0)),
        ("pour A into B", (a - into_b, b + into_b)),
        ("pour B into A", (a + into_a, b - into_a)),
    ]
    return [(name, state) for name, state in options if state != (a, b)]


print("from (3, 2):", moves(3, 2))

start = (0, 0)
seen = {start}
stack = [start]
while stack:
    state = stack.pop()
    for _, nxt in moves(*state):
        if nxt not in seen:
            seen.add(nxt)
            stack.append(nxt)

print(len(seen), "of", (A + 1) * (B + 1), "pairs can be reached from", start)
edges = [(s, nxt) for s in seen for _, nxt in moves(*s)]
one_way = [(s, nxt) for s, nxt in edges if s not in [back for _, back in moves(*nxt)]]
print(len(edges), "moves between them,", len(one_way), "of them one-way, for example", min(one_way))
print("states with 4 litres in a jug:", sorted(s for s in seen if 4 in s))
print("never reached:", sorted((a, b) for a in range(A + 1) for b in range(B + 1) if (a, b) not in seen))

from (3, 2): [('fill B', (3, 5)), ('empty A', (0, 2)), ('empty B', (3, 0)), ('pour A into B', (0, 5))]
16 of 24 pairs can be reached from (0, 0)
58 moves between them, 24 of them one-way, for example ((0, 1), (0, 0))
states with 4 litres in a jug: [(0, 4), (3, 4)]
never reached: [(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4)]

What the run shows:

• moves() is the whole graph. It makes the neighbours of one state on request, and no list is ever built. From (3, 2) four moves change something; filling A again or pouring B into the full A would leave the state as it is, so they are dropped.
• Only 16 of the 24 pairs can be reached from (0, 0). Every move leaves at least one jug empty or full: filling and emptying do so directly, and a pour stops exactly when the first jug is empty or the second is full. The 8 pairs with both jugs partly full, on the last line of the output, never appear.
• 24 of the 58 moves are one-way. Emptying B turns (0, 1) into (0, 0), and no single move turns (0, 0) back into (0, 1). This graph is directed, and a model that stored every move in both directions would let a search walk backwards along moves the puzzle does not allow.
• Two reachable states hold 4 litres, so the puzzle can be solved. How few moves it takes is a shortest-path question, which the next lesson of this module answers.

Storing a graph: the adjacency list

When the input lists the edges, as most graph problems in coding rounds do, you hold an edge list: one pair per edge. An edge list is all that union-find needs. But it answers “which nodes are next to u?” only by reading every pair, and a search asks that question for every node it reaches. So a search wants the answers prepared in advance, as an adjacency list: an array of n lists in which list u holds every node that an edge leads to from u.

Here is a fictional city’s night metro. Each station is a node, each stretch of track between two stops that are next to each other on a line is an edge, and trains run both ways:

"""A fictional city's night metro as a graph: stations are nodes, the track between two stops is an edge."""

STATIONS = ["Amber Park", "Bell Square", "Canal Street", "Dock Gate", "Elm Cross", "Fair Lane", "Granary", "Hill Top"]
LINES = {
    "Red": ["Amber Park", "Bell Square", "Canal Street", "Dock Gate"],
    "Blue": ["Bell Square", "Elm Cross", "Fair Lane", "Dock Gate"],
    "Green": ["Granary", "Hill Top"],
}

number = {name: i for i, name in enumerate(STATIONS)}  # names to node numbers 0 to n - 1

# The edge list: one (u, v, line) for each pair of stops next to each other on a line.
segments = []
for line, stops in LINES.items():
    for a, b in zip(stops, stops[1:]):
        segments.append((number[a], number[b], line))

# The adjacency list: for every station, the stations one segment away, with the line that runs there.
adj = [[] for _ in STATIONS]
for u, v, line in segments:
    adj[u].append((v, line))  # trains run both ways,
    adj[v].append((u, line))  # so every segment goes into two lists

for u, name in enumerate(STATIONS):
    print(f"{u} {name:<12} -> " + ", ".join(f"{v} {STATIONS[v]} ({line})" for v, line in adj[u]))

print(len(segments), "segments,", sum(len(row) for row in adj), "entries in the lists")
print("interchanges:", [STATIONS[u] for u, row in enumerate(adj) if len({line for _, line in row}) > 1])

0 Amber Park   -> 1 Bell Square (Red)
1 Bell Square  -> 0 Amber Park (Red), 2 Canal Street (Red), 4 Elm Cross (Blue)
2 Canal Street -> 1 Bell Square (Red), 3 Dock Gate (Red)
3 Dock Gate    -> 2 Canal Street (Red), 5 Fair Lane (Blue)
4 Elm Cross    -> 1 Bell Square (Blue), 5 Fair Lane (Blue)
5 Fair Lane    -> 4 Elm Cross (Blue), 3 Dock Gate (Blue)
6 Granary      -> 7 Hill Top (Green)
7 Hill Top     -> 6 Granary (Green)
7 segments, 14 entries in the lists
interchanges: ['Bell Square', 'Dock Gate']

Three things in this output deserve a second look:

• Each entry is a pair: the station that a segment leads to and the line that runs there. Whatever you know about an edge travels with it this way: a line here, a travel time or a fare in a weighted graph.
• Building the lists is one pass over the segments, O(V + E) time and memory: eight empty lists, then two appends for every two-way segment.
• Seven segments became 14 entries. An undirected edge is stored once in the list of each of its two ends, so the lists of an undirected graph hold exactly 2E entries, which is also the sum of all the degrees. A search that reads each list at most once reads at most 2E entries, and that is where the E in O(V + E) comes from.

The other common representation is the adjacency matrix, a V × V table with a mark at (u, v) when an edge runs from u to v. It answers “is there an edge from u to v?” in O(1), but it costs V² cells however few edges there are: 4 × 10¹⁰ cells for 200,000 stations, whose lists need only 400,000 entries for 200,000 segments. The graphs of coding rounds are nearly always sparse, with far fewer edges than possible pairs, so build lists unless V is small and most pairs are joined. The Data Structures & Algorithms (DSA) track covers the representations themselves.

Adjacency lists in five languages

Every language builds the lists the same way: n empty lists, then one append for each end of each edge. This is how each one makes the lists and adds the edge between u and v:

• Python: adj = [[] for _ in range(n)], then adj[u].append(v) and adj[v].append(u).
• JavaScript: const adj = Array.from({ length: n }, () => []), then adj[u].push(v) and adj[v].push(u).
• Java: List<List<Integer>> adj = new ArrayList<>(n), then adj.add(new ArrayList<>()) n times; an edge is adj.get(u).add(v) and adj.get(v).add(u).
• C++: std::vector<std::vector<int>> adj(n), then adj[u].push_back(v) and adj[v].push_back(u).
• Go: adj := make([][]int, n), then adj[u] = append(adj[u], v) and adj[v] = append(adj[v], u).

Every language also offers a way to make the n empty lists that looks right, runs, and breaks the graph. Each program below builds the night metro’s lists the right way and prints them, then falls into its language’s trap and prints what happened:

"""The night metro's adjacency list in Python, and what [[]] * n does instead."""

n = 8
segments = [(0, 1), (1, 2), (2, 3), (1, 4), (4, 5), (5, 3), (6, 7)]


def build(n, segments):
    adj = [[] for _ in range(n)]  # the comprehension makes a new list for every station
    for u, v in segments:
        adj[u].append(v)
        adj[v].append(u)
    return adj


print("right:", build(n, segments))

trap = [[]] * n  # one list, listed n times
for u, v in segments:
    trap[u].append(v)
    trap[v].append(u)
print("trap: ", len(trap[0]), "neighbours for station 0; one list for all?", trap[0] is trap[7])

right: [[1], [0, 2, 4], [1, 3], [2, 5], [1, 5], [4, 3], [7], [6]]
trap:  14 neighbours for station 0; one list for all? True

// The night metro's adjacency list in JavaScript, and what fill([]) does instead.

const n = 8;
const segments = [[0, 1], [1, 2], [2, 3], [1, 4], [4, 5], [5, 3], [6, 7]];

function build(n, segments) {
  const adj = Array.from({ length: n }, () => []); // the callback makes a new array for every station
  for (const [u, v] of segments) {
    adj[u].push(v);
    adj[v].push(u);
  }
  return adj;
}

console.log('right:', JSON.stringify(build(n, segments)));

const trap = new Array(n).fill([]); // fill puts the same array in every slot
for (const [u, v] of segments) {
  trap[u].push(v);
  trap[v].push(u);
}
console.log('trap: ', trap[0].length, 'neighbours for station 0; one array for all?', trap[0] === trap[7]);

right: [[1],[0,2,4],[1,3],[2,5],[1,5],[4,3],[7],[6]]
trap:  14 neighbours for station 0; one array for all? true

import java.util.ArrayList;
import java.util.List;

/** The night metro's adjacency list in Java, and what new ArrayList<>(n) does instead. */
public class Build {
    static List<List<Integer>> build(int n, int[][] segments) {
        List<List<Integer>> adj = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>()); // n empty lists, added one by one
        }
        for (int[] s : segments) {
            adj.get(s[0]).add(s[1]);
            adj.get(s[1]).add(s[0]);
        }
        return adj;
    }

    public static void main(String[] args) {
        int n = 8;
        int[][] segments = {{0, 1}, {1, 2}, {2, 3}, {1, 4}, {4, 5}, {5, 3}, {6, 7}};
        System.out.println("right: " + build(n, segments));

        List<List<Integer>> trap = new ArrayList<>(n); // room for n lists, but it holds none yet
        try {
            trap.get(0).add(1);
        } catch (IndexOutOfBoundsException e) {
            System.out.println("trap:  " + e.getMessage());
        }
    }
}

// The night metro's adjacency list in C++, and what station numbers from 1 to n do to it.
#include <print>
#include <stdexcept>
#include <utility>
#include <vector>

std::vector<std::vector<int>> build(int n, const std::vector<std::pair<int, int>>& segments) {
    std::vector<std::vector<int>> adj(n);  // n empty vectors
    for (auto [u, v] : segments) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    return adj;
}

int main() {
    std::vector<std::pair<int, int>> segments{{0, 1}, {1, 2}, {2, 3}, {1, 4}, {4, 5}, {5, 3}, {6, 7}};
    auto adj = build(8, segments);
    std::println("right: {}", adj);  // C++23 formats a vector of vectors

    // Input that numbers the stations 1 to 8 needs 9 slots. at() checks the index; adj[8] would not.
    try {
        adj.at(8).push_back(7);
    } catch (const std::out_of_range&) {
        std::println("trap:  at(8) threw std::out_of_range: the vector has {} slots, 0 to {}", adj.size(), adj.size() - 1);
    }
}

// The night metro's adjacency list in Go, and what make([][]int, 0, n) does instead.
package main

import "fmt"

func build(n int, segments [][2]int) [][]int {
	adj := make([][]int, n) // n nil slices: append gives each one an array when it needs one
	for _, s := range segments {
		u, v := s[0], s[1]
		adj[u] = append(adj[u], v)
		adj[v] = append(adj[v], u)
	}
	return adj
}

func main() {
	segments := [][2]int{{0, 1}, {1, 2}, {2, 3}, {1, 4}, {4, 5}, {5, 3}, {6, 7}}
	fmt.Println("right:", build(8, segments))

	defer func() { fmt.Println("trap: ", recover()) }()
	trap := make([][]int, 0, 8) // length 0, capacity 8
	trap[0] = append(trap[0], 1)
}

from session import run, versions

# Build.java runs as a single source file, build.cpp is compiled with the sanitizers on, and go run compiles build.go.
versions("java -version", "clang++ --version", "go version")
run("""
java Build.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined build.cpp -o build && ./build
go run build.go
""")

# openjdk version "25.0.4.1" LTS
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ java Build.java
right: [[1], [0, 2, 4], [1, 3], [2, 5], [1, 5], [4, 3], [7], [6]]
trap:  Index 0 out of bounds for length 0
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined build.cpp -o build && ./build
right: [[1], [0, 2, 4], [1, 3], [2, 5], [1, 5], [4, 3], [7], [6]]
trap:  at(8) threw std::out_of_range: the vector has 8 slots, 0 to 7
$ go run build.go
right: [[1] [0 2 4] [1 3] [2 5] [1 5] [4 3] [7] [6]]
trap:  runtime error: index out of range [0] with length 0

All five print the same lists; Go separates the numbers with spaces instead of commas. The traps:

• Python. [[]] * n copies references, not lists. The Python FAQ puts it plainly: replicating a list with * makes references to the existing objects, not copies. All eight stations append to one list, which collects all 14 entries. It is the trap of the grid conventions lesson again, one level up; the comprehension evaluates [] afresh for every station.
• JavaScript. MDN notes that when fill is given an object, every slot of the array refers to that same object, so all eight slots hold one array. Array.from calls its function once for each index, and every call returns a new array.
• Java. The number passed to new ArrayList<>(n) is an initial capacity, and the documentation says that the constructor makes an empty list: room for n lists, but none of them there yet. get(0) throws IndexOutOfBoundsException until a loop has added the n lists.
• C++. adj(n) makes n empty vectors, but input that numbers the nodes from 1 to n uses index n, one past the end. at() checks the index and throws std::out_of_range, as the run shows; adj[8] checks nothing, and writing through it is undefined behaviour. Make n + 1 lists and leave slot 0 empty, or subtract 1 from every node as you read it.
• Go. make([][]int, n) makes n nil slices, and append gives each one an underlying array the first time it needs one. make([][]int, 0, n) has length 0 and only a capacity of n, so trap[0] is out of range, which the Go specification makes a run-time panic.

Choosing the search for the question

Once the lists exist, the question in the statement picks the search. This module uses three:

• BFS takes nodes from a queue, first in, first out, so it reaches them in order of their distance from the start: every node one edge away, then every node two edges away, and so on. The first time it reaches a node, it has come along the fewest edges.
• DFS takes them from a stack, your own or the call stack of a recursive function, so it follows one path as deep as it goes before it backs up. That order is what cycle checks and orderings need.
• Union-find does not walk the graph at all. It keeps the nodes in groups and merges two groups for each edge, so it can say whether two nodes are connected at any moment while edges keep arriving, in nearly constant time per operation averaged over a long run of them, as Tarjan’s analysis in the references shows.

Which one to use depends on the question:

• Can s reach t, and which nodes can it reach? Any of the three: BFS or DFS in O(V + E), or union-find once every edge has been merged.
• How few edges lead from s to t? Only BFS, because its first visit to a node comes along a shortest route. The first route a DFS finds can be long, and union-find keeps no routes at all.
• How many groups are there, and how big is each? BFS or DFS started from every node that is still unmarked, or union-find, which counts the groups while it merges them.
• Edges keep arriving, with questions in between? Union-find, which handles each merge and each question as it comes, while BFS and DFS would need a new search for every question.
• Cycles or an order in a directed graph? DFS, with node colours and the order in which nodes finish; or counts of incoming edges, in the topological sort module. Union-find ignores direction, so it cannot answer.
• Memory: each needs O(V) besides the graph: a queue or a stack with the marks, or a parent for every node.

When the edges have different costs, none of the three finds the cheapest route. Dijkstra’s algorithm does, provided no cost is negative, and the weighted-graphs module of this track covers it.

The problem below asks only whether a passenger can get through, which needs no route and no distance, so any of the three would do. The solution uses DFS with an explicit stack: it is the shortest code in all five languages, and it cannot run out of call stack the way a recursive search can on a long line of stations. In Python, a recursion that deep stops with a RecursionError at the interpreter’s recursion limit, which is there so that runaway recursion cannot overflow the C stack and crash Python.

A problem solved in full: the night network

Four examples, which every version of the code below runs; the first three use the metro of the diagram above:

1. From 0 Amber Park to 5 Fair Lane: True. The Red line goes to Bell Square, then the Blue line through Elm Cross.
2. From 3 Dock Gate to 7 Hill Top: False. No segment joins the Green line to the other six stations.
3. From 6 Granary to 6 Granary: True, without travelling at all.
4. n = 4 and segments = [(0, 1), (1, 0), (1, 2)], from 0 to 3: False. The repeated segment changes nothing, and station 3 has no segment.

The brute force: reread every segment

The simplest search keeps a mark for every station reached and a stack of stations still to look at. To find the neighbours of the station it takes from the stack, it reads the whole list of segments and keeps the ones that touch that station. It is correct, and reachable_slow in the check at the end of this section is that code. But every station it takes costs a full pass over the segments, so it makes up to n × m segment reads for n stations and m segments: 4 × 10¹⁰ at n = m = 200,000. With the budgets from the lesson on constraints, about 10⁸ simple steps a second for C++ and 10⁷ for CPython, that is more than six minutes of C++ and more than an hour of Python.

What to notice

The slow part is one question asked over and over: which segments touch station u? Its answer never changes during the search, so work it out once for every station before the search starts. That is the adjacency list. With it, each station costs only its own degree, the degrees add up to 2m, and the whole search reads at most 2m entries.

The search in O(V + E)

1. Build the adjacency list: n empty lists, then both directions of every segment.
2. Mark start and push it onto a stack.
3. Pop a station u. If u is goal, return True.
4. Otherwise read the list of u, and mark and push every neighbour that is not marked yet.
5. Go back to step 3 while the stack is not empty; when it is empty, return False.

Why it is correct

The loop keeps one invariant: every marked station can be reached from start, and every marked station whose list has not been read is on the stack. Three arguments, in the style of the lesson on dry runs and invariants, show that the search is right:

1. The invariant holds at the start. Only start is marked, it reaches itself, and it is on the stack.
2. Every step keeps it. A station is marked only when a segment joins it to the station just popped, which can be reached, so the newly marked station can be reached too, and it is pushed at the moment it is marked. A popped station leaves the stack in the same step that reads its list.
3. Nothing reachable is missed. Suppose the stack is empty while some station on a route from start is still unmarked, and take the first such station on the route. The station just before it is marked, so it was pushed, popped and had its list read, and that list contains the unmarked station, which the loop would then have marked. So once the stack is empty, every station that start can reach is marked. Had goal been one of them, it would have been pushed and popped, and the search would have returned True, so False is the right answer.

The cost follows from the marks. A station is pushed only when it is marked and is never unmarked, so each station is pushed and popped at most once and each list is read at most once: at most n pops and 2m list reads, after m reads to build the lists. That is O(n + m) time, and O(n + m) memory for the lists, the marks and the stack. Tarjan’s paper on depth-first search, in the references, is the classic source for linear-time searches over adjacency lists like this one.

A dry run

"""A dry run of the search on the night metro: one row for each station taken from the stack."""
from collections import deque

METRO = [(0, 1), (1, 2), (2, 3), (1, 4), (4, 5), (5, 3), (6, 7)]
adj = [[] for _ in range(8)]
for u, v in METRO:
    adj[u].append(v)
    adj[v].append(u)


def trace(start, goal):
    print(f"from {start} to {goal}")
    print(f"{'take':>4}  {'its list':<10} {'pushed':<8} {'stack':<8} marked")
    seen = {start}
    stack = [start]
    while stack:
        u = stack.pop()
        if u == goal:
            print(f"{u:>4}  the goal: True")
            return
        pushed = []
        for v in adj[u]:  # the same loop as reachable()
            if v not in seen:
                seen.add(v)
                stack.append(v)
                pushed.append(v)
        print(f"{u:>4}  {str(adj[u]):<10} {str(pushed):<8} {str(stack):<8} {sorted(seen)}")
    print("      the stack is empty: False")


trace(0, 5)
trace(3, 7)


def order(start, take):
    """The order in which stations leave the to-do list, all of them, with a stack or a queue."""
    seen, todo, out = {start}, deque([start]), []
    while todo:
        u = take(todo)
        out.append(u)
        for v in adj[u]:
            if v not in seen:
                seen.add(v)
                todo.append(v)
    return out


print("stack order from 3:", order(3, deque.pop))
print("queue order from 3:", order(3, deque.popleft))

from 0 to 5
take  its list   pushed   stack    marked
   0  [1]        [1]      [1]      [0, 1]
   1  [0, 2, 4]  [2, 4]   [2, 4]   [0, 1, 2, 4]
   4  [1, 5]     [5]      [2, 5]   [0, 1, 2, 4, 5]
   5  the goal: True
from 3 to 7
take  its list   pushed   stack    marked
   3  [2, 5]     [2, 5]   [2, 5]   [2, 3, 5]
   5  [4, 3]     [4]      [2, 4]   [2, 3, 4, 5]
   4  [1, 5]     [1]      [2, 1]   [1, 2, 3, 4, 5]
   1  [0, 2, 4]  [0]      [2, 0]   [0, 1, 2, 3, 4, 5]
   0  [1]        []       [2]      [0, 1, 2, 3, 4, 5]
   2  [1, 3]     []       []       [0, 1, 2, 3, 4, 5]
      the stack is empty: False
stack order from 3: [3, 5, 4, 1, 0, 2]
queue order from 3: [3, 2, 5, 1, 4, 0]

In the first trace, Amber Park’s list holds only Bell Square, which is marked and pushed. Bell Square’s list adds Canal Street and Elm Cross, and Amber Park is skipped because it is marked already. Elm Cross comes off the stack next, because a stack returns the newest station first, and it adds Fair Lane, the goal, which ends the search when it is popped. The second trace reads the list of all six connected stations and ends with an empty stack. Dock Gate is marked once although both Canal Street and Fair Lane lead back to it: without the marks, the loop through Bell Square, Canal Street, Dock Gate, Fair Lane and Elm Cross would push stations forever. The last two lines show a queue visiting the same six stations in another order. Reachability does not depend on the order; the fewest steps do, which is why BFS uses a queue.

The code in five languages

"""Can a passenger get from start to goal? An adjacency list, then a search with an explicit stack: O(n + m)."""


def reachable(n, segments, start, goal):
    adj = [[] for _ in range(n)]
    for u, v in segments:
        adj[u].append(v)
        adj[v].append(u)
    seen = [False] * n
    seen[start] = True
    stack = [start]
    # Invariant: every station marked in seen can be reached from start,
    # and every marked station whose list is not read yet is on the stack.
    while stack:
        u = stack.pop()
        if u == goal:
            return True
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True  # marked when pushed, so no station is pushed twice
                stack.append(v)
    return False


METRO = [(0, 1), (1, 2), (2, 3), (1, 4), (4, 5), (5, 3), (6, 7)]
print(reachable(8, METRO, 0, 5))  # Amber Park to Fair Lane
print(reachable(8, METRO, 3, 7))  # Dock Gate to Hill Top
print(reachable(8, METRO, 6, 6))  # Granary to Granary
print(reachable(4, [(0, 1), (1, 0), (1, 2)], 0, 3))  # a segment listed twice, a station with none

True
False
True
False

// Can a passenger get from start to goal? An adjacency list, then a search with an explicit stack: O(n + m).

function reachable(n, segments, start, goal) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of segments) {
    adj[u].push(v);
    adj[v].push(u);
  }
  const seen = new Uint8Array(n); // all 0: nothing marked yet
  seen[start] = 1;
  const stack = [start];
  // Invariant: every marked station can be reached from start,
  // and every marked station whose list is not read yet is on the stack.
  while (stack.length > 0) {
    const u = stack.pop();
    if (u === goal) return true;
    for (const v of adj[u]) {
      if (!seen[v]) {
        seen[v] = 1; // marked when pushed, so no station is pushed twice
        stack.push(v);
      }
    }
  }
  return false;
}

const METRO = [[0, 1], [1, 2], [2, 3], [1, 4], [4, 5], [5, 3], [6, 7]];
console.log(reachable(8, METRO, 0, 5)); // Amber Park to Fair Lane
console.log(reachable(8, METRO, 3, 7)); // Dock Gate to Hill Top
console.log(reachable(8, METRO, 6, 6)); // Granary to Granary
console.log(reachable(4, [[0, 1], [1, 0], [1, 2]], 0, 3)); // a segment listed twice, a station with none

true
false
true
false

import java.util.ArrayList;
import java.util.List;

/** Can a passenger get from start to goal? An adjacency list, then a search with an explicit stack: O(n + m). */
public class Reach {
    static boolean reachable(int n, int[][] segments, int start, int goal) {
        List<List<Integer>> adj = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] s : segments) {
            adj.get(s[0]).add(s[1]);
            adj.get(s[1]).add(s[0]);
        }
        boolean[] seen = new boolean[n]; // all false
        int[] stack = new int[n]; // a station is pushed at most once, so n slots are enough
        int top = 0;
        seen[start] = true;
        stack[top++] = start;
        // Invariant: every marked station can be reached from start,
        // and every marked station whose list is not read yet is on the stack.
        while (top > 0) {
            int u = stack[--top];
            if (u == goal) {
                return true;
            }
            for (int v : adj.get(u)) {
                if (!seen[v]) {
                    seen[v] = true; // marked when pushed, so no station is pushed twice
                    stack[top++] = v;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] metro = {{0, 1}, {1, 2}, {2, 3}, {1, 4}, {4, 5}, {5, 3}, {6, 7}};
        System.out.println(reachable(8, metro, 0, 5)); // Amber Park to Fair Lane
        System.out.println(reachable(8, metro, 3, 7)); // Dock Gate to Hill Top
        System.out.println(reachable(8, metro, 6, 6)); // Granary to Granary
        System.out.println(reachable(4, new int[][] {{0, 1}, {1, 0}, {1, 2}}, 0, 3)); // a repeated segment
    }
}

// Can a passenger get from start to goal? An adjacency list, then a search with an explicit stack: O(n + m).
#include <print>
#include <utility>
#include <vector>

bool reachable(int n, const std::vector<std::pair<int, int>>& segments, int start, int goal) {
    std::vector<std::vector<int>> adj(n);
    for (auto [u, v] : segments) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    std::vector<char> seen(n, 0);  // char rather than bool: std::vector<bool> packs bits
    std::vector<int> stack{start};
    seen[start] = 1;
    // Invariant: every marked station can be reached from start,
    // and every marked station whose list is not read yet is on the stack.
    while (!stack.empty()) {
        int u = stack.back();
        stack.pop_back();
        if (u == goal) return true;
        for (int v : adj[u]) {
            if (!seen[v]) {
                seen[v] = 1;  // marked when pushed, so no station is pushed twice
                stack.push_back(v);
            }
        }
    }
    return false;
}

int main() {
    std::vector<std::pair<int, int>> metro{{0, 1}, {1, 2}, {2, 3}, {1, 4}, {4, 5}, {5, 3}, {6, 7}};
    std::println("{}", reachable(8, metro, 0, 5));  // Amber Park to Fair Lane
    std::println("{}", reachable(8, metro, 3, 7));  // Dock Gate to Hill Top
    std::println("{}", reachable(8, metro, 6, 6));  // Granary to Granary
    std::println("{}", reachable(4, {{0, 1}, {1, 0}, {1, 2}}, 0, 3));  // a repeated segment
}

// Can a passenger get from start to goal? An adjacency list, then a search with an explicit stack: O(n + m).
package main

import "fmt"

func reachable(n int, segments [][2]int, start, goal int) bool {
	adj := make([][]int, n)
	for _, s := range segments {
		u, v := s[0], s[1]
		adj[u] = append(adj[u], v)
		adj[v] = append(adj[v], u)
	}
	seen := make([]bool, n) // all false
	seen[start] = true
	stack := []int{start}
	// Invariant: every marked station can be reached from start,
	// and every marked station whose list is not read yet is on the stack.
	for len(stack) > 0 {
		u := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if u == goal {
			return true
		}
		for _, v := range adj[u] {
			if !seen[v] {
				seen[v] = true // marked when pushed, so no station is pushed twice
				stack = append(stack, v)
			}
		}
	}
	return false
}

func main() {
	metro := [][2]int{{0, 1}, {1, 2}, {2, 3}, {1, 4}, {4, 5}, {5, 3}, {6, 7}}
	fmt.Println(reachable(8, metro, 0, 5))                            // Amber Park to Fair Lane
	fmt.Println(reachable(8, metro, 3, 7))                            // Dock Gate to Hill Top
	fmt.Println(reachable(8, metro, 6, 6))                            // Granary to Granary
	fmt.Println(reachable(4, [][2]int{{0, 1}, {1, 0}, {1, 2}}, 0, 3)) // a repeated segment
}

from session import run, versions

# The same four examples in Java, C++ and Go: Reach.java as a single source file, reach.cpp with the sanitizers on.
versions("java -version", "clang++ --version", "go version")
run("""
java Reach.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined reach.cpp -o reach && ./reach
go run reach.go
""")

# openjdk version "25.0.4.1" LTS
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ java Reach.java
true
false
true
false
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined reach.cpp -o reach && ./reach
true
false
true
false
$ go run reach.go
true
false
true
false

• Python and JavaScript use the list or array itself as the stack: items go on and come off at its end. The Python documentation gives append and pop at the end of a list an O(1) cost, while every item taken from the front costs O(n), which matters for the queue of a BFS but not for this stack.
• Java keeps the stack in an int[] of n slots, which is enough because a station is pushed at most once. C++ and Go grow a vector and a slice and pop from their back.
• The marks are a boolean[], a std::vector<char>, a []bool, a Uint8Array and a Python list. A set would work too, but when the nodes are numbered 0 to n − 1, an array indexed by node is usually smaller and faster.
• No number comes near the 32-bit limit: stations are numbered below 200,000 and the stack never holds more than n entries, so a plain int is safe in Java and C++.

Checking it against the brute force

"""The search without an adjacency list, as a judge for the fast one, and what each costs on a long line."""
import random


def reachable_slow(n, segments, start, goal):
    """No adjacency list: to find the neighbours of a station, read every segment."""
    seen = [False] * n
    seen[start] = True
    stack = [start]
    reads = 0
    while stack:
        u = stack.pop()
        if u == goal:
            return True, reads
        for a, b in segments:  # all m segments, again for every station taken
            reads += 1
            v = b if a == u else a if b == u else None
            if v is not None and not seen[v]:
                seen[v] = True
                stack.append(v)
    return False, reads


def reachable(n, segments, start, goal):
    """The adjacency list first (one read per segment), then each list read once at most."""
    adj = [[] for _ in range(n)]
    reads = 0
    for u, v in segments:
        reads += 1
        adj[u].append(v)
        adj[v].append(u)
    seen = [False] * n
    seen[start] = True
    stack = [start]
    while stack:
        u = stack.pop()
        if u == goal:
            return True, reads
        for v in adj[u]:
            reads += 1
            if not seen[v]:
                seen[v] = True
                stack.append(v)
    return False, reads


rng = random.Random(7)
agree = found = 0
for _ in range(3000):
    n = rng.randint(1, 9)
    segments = [tuple(rng.sample(range(n), 2)) for _ in range(rng.randint(0, 14))] if n > 1 else []
    start, goal = rng.randrange(n), rng.randrange(n)
    slow, fast = reachable_slow(n, segments, start, goal)[0], reachable(n, segments, start, goal)[0]
    agree += slow == fast
    found += fast
print(f"3000 random networks: the two agree on {agree}; {found} have a route, {3000 - found} do not")

print(f"{'n':>6} {'reads, no lists':>16} {'reads, lists':>13}")
for n in (250, 500, 1000):
    line = [(i, i + 1) for i in range(n - 1)]  # 0 - 1 - 2 - ... - (n - 1), searched from one end to the other
    print(f"{n:>6,} {reachable_slow(n, line, 0, n - 1)[1]:>16,} {reachable(n, line, 0, n - 1)[1]:>13,}")
n = m = 200_000
print(f"at n = m = 200,000 the counts would be about {n * m:,} and {3 * m:,}")

3000 random networks: the two agree on 3000; 2325 have a route, 675 do not
     n  reads, no lists  reads, lists
   250           62,001           746
   500          249,001         1,496
 1,000          998,001         2,996
at n = m = 200,000 the counts would be about 40,000,000,000 and 600,000

The two versions agree on all 3,000 random networks. They are small on purpose, with repeated segments and stations that have none, so both answers come up hundreds of times. The counts come from a line of stations searched from one end to the other. The brute force reads (n − 1)² segments, 62,001 at n = 250 and 998,001 at n = 1,000, about four times as many whenever n doubles, while the adjacency-list version reads 3n − 4 entries, which only doubles. At the problem’s limits that is about 4 × 10¹⁰ reads against about 600,000.

Interview questions

In a grid maze, what are the nodes and the edges, and why do you usually not build an adjacency list for it? (warm-up)

Every open cell (r, c) is a node, and an edge joins two open cells that touch: up, down, left or right, or also diagonally when the rules allow it. Walls are cells that are not nodes. A step can always be taken back, so the graph is undirected. You rarely build its adjacency list because the grid already holds that information: a cell’s neighbours are a few index sums and a bounds check away, so the search can work them out when it reaches the cell. Copying them into lists would cost time and memory for nothing, up to four entries per cell, close to four million on a 1,000 × 1,000 grid. Build lists only when the moves are not plain grid steps, for example when some cells are linked by teleporters.

Why do the adjacency lists of an undirected graph with E edges hold 2E entries, and what does that mean for the cost of a search? (warm-up)

An undirected edge between u and v can be followed both ways, so building the lists appends v to the list of u and u to the list of v: two entries for every edge, 2E in all, which is also the sum of all the degrees. A directed graph stores each edge once, E entries. A search marks each node once and reads the list of each node it reaches once, so it does O(V) work for the nodes and at most 2E reads for the edges: O(V + E) in total. A node with 10,000 neighbours therefore costs 10,000 reads once, not on every visit. An edge listed twice in the input adds four entries, which a search does not mind but a degree count does.

Key takeaways

• A node carries everything that decides the next move, and an edge is one allowed step. Whether steps run both ways and what they cost decide which searches are correct.
• Count V and E before you code: every search in this module costs O(V + E).
• Build an adjacency list in one pass over the edges. An undirected edge goes into both lists, so the lists hold 2E entries. Grids and puzzles rarely need lists: work out the neighbours when the search asks.
• Making n empty lists has one trap per language: [[]] * n, fill([]), a bare new ArrayList<>(n), one slot too few for nodes numbered from 1, and make([][]int, 0, n).
• BFS for the fewest steps, BFS or DFS for reachability and groups, union-find while edges keep arriving. An explicit stack answers reachability in O(V + E) without any risk of overflowing the call stack.