Graphs III — Topological Sort

Review boundary and corrected contracts

A topological order is defined for directed acyclic constraints. Kahn indegrees count remaining incoming edges, including multiplicity; emit a node once when its count reaches zero. An empty output can mean either an empty graph or a cycle, so callers needing the distinction should return a separate status.

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.

Learning objective: Write Kahn's algorithm from memory, use the count of emitted nodes as a cycle detector, and recognise dependency-ordering problems even when the word 'graph' never appears.

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

Why this session exists

Two questions that look completely different turn out to be the same question: "in what order can I do these tasks" and "is there a circular dependency". Topological sort answers both with one pass, and the second answer falls out of the first for free.

That is the elegance worth internalising. You do not write a cycle detector and then a sorter. You write Kahn's algorithm, and if it emits fewer than n nodes, the leftovers are nodes on cycles and nodes downstream of those cycles. A downstream node can be blocked without belonging to any cycle. One algorithm, two answers, no extra code.

The reason this appears so often in practice is that dependency ordering is a real problem that real systems solve constantly — build systems, package managers, task schedulers, spreadsheet recalculation, database migrations. Course Schedule is a thin disguise over something a reviewer's team ships.

Blank-file warm-up

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

indeg = [0] * n           — count incoming edges
q = deque(nodes with indeg == 0)
pop, emit, decrement neighbours, push the new zeros

Specifically: given n and prerequisites = [[a, b], ...] meaning you must take b before a, produce a valid ordering or an empty list if impossible.

What wobbles from memory: the edge direction. [a, b] with "take b before a" means the edge runs b → a, so indeg[a] increments, not indeg[b]. Getting that backwards produces a perfectly valid topological order of the reversed graph, which is wrong and looks right.

Pattern anatomy

The shape of problem that summons topological sort: a set of items plus constraints of the form "X must come before Y", and a question about ordering or feasibility. The graph must be directed. If the edges are undirected there is no notion of "before" and this pattern does not apply.

The invariant: between iterations, the queue contains exactly the not-yet-emitted nodes whose remaining in-degree is zero. A node's in-degree is the number of its prerequisites not yet satisfied. When that count hits zero, the node becomes legal to emit. That is the whole algorithm.

The template:

from collections import deque, defaultdict
 
def topo_sort(n, edges):
    """edges = [(u, v)] meaning u must come BEFORE v."""
    adj = defaultdict(list)
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1                     # v gains an unsatisfied prerequisite
 
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nxt in adj[node]:
            indeg[nxt] -= 1               # one prerequisite satisfied
            if indeg[nxt] == 0:
                q.append(nxt)             # push exactly when it hits zero
 
    return order if len(order) == n else []   # short order == cycle

Two lines carry all the meaning.

if indeg[nxt] == 0 detects the one transition to zero under a correctly balanced adjacency/in-degree representation. Duplicate edges are safe when counted once per occurrence in both structures. Under that invariant, <= 0 behaves identically; equality is not a repair for miscounted edges, which can emit a node too early even with == 0.

return order if len(order) == n else [] — this is the cycle detector. Nodes in a cycle mutually hold each other's in-degree above zero forever, so none of them ever enters the queue. If you emitted fewer than n, the missing ones lie on, or are reachable from, a cycle. In 0→1, 1→0, 1→2, node 2 is blocked downstream; an upstream node pointing into this cycle can still be emitted.

The DFS alternative, which produces a reverse post-order, is worth knowing but is not what I reach for:

def topo_dfs(n, adj):
    WHITE, GREY, BLACK = 0, 1, 2
    color = [WHITE] * n
    out = []
 
    def visit(u):
        if color[u] == GREY:
            return False                 # back edge -> cycle
        if color[u] == BLACK:
            return True
        color[u] = GREY
        for v in adj[u]:
            if not visit(v):
                return False
        color[u] = BLACK
        out.append(u)                    # append AFTER children: post-order
        return True
 
    for u in range(n):
        if not visit(u):
            return []
    return out[::-1]

Three colours, not two. GREY means "on the current recursion stack" and hitting a grey node is a back edge, which is a cycle. A two-state visited set cannot distinguish "already fully processed" from "currently being processed", and that distinction is the whole cycle test.

The cue

You are looking at a topological sort when the statement contains one of these tells:

1. "Prerequisites", "dependencies", "must come before", "requires". Course Schedule, Build Order, Task Scheduling. The phrasing is almost always literal.
2. "Is it possible to finish all / complete all" — a yes/no feasibility question over a dependency set. That is cycle detection, and Kahn answers it with the emitted-count check.
3. "Return any valid order" or "return the lexicographically smallest valid order". The second variant is the same algorithm with a min-heap instead of a deque.
4. Deriving an order from partial observations — Alien Dictionary. You are given evidence of pairwise precedence and asked to reconstruct a total order consistent with it.
5. Directed precedence constraints plus ordering. Direction alone is not enough: reachability and strongly connected components are different tasks. Topological order also supports shortest/longest-path DP on a DAG, including weighted DAGs.

The negative cue: an undirected edge by itself does not specify a precedence constraint. If the edges are symmetric, "before" is undefined. If you find yourself appending edges in both directions while writing a topological sort, you have misread the problem.

Guided solve

Course Schedule. numCourses courses labelled 0 to n−1, and prerequisites[i] = [a, b] meaning you must take course b before course a. Return whether you can finish all courses.

First, translate. "Must take b before a" means the dependency edge runs from b to a. So in my (u, v) convention where u comes before v, the pair [a, b] maps to u = b, v = a. Write this down before touching the keyboard, because reversing it silently is the single most common failure on this problem.

Second, restate the question. "Can you finish all courses" means "does a valid ordering exist", which means "is the dependency graph acyclic". So the answer is len(order) == numCourses.

from collections import deque, defaultdict
 
def canFinish(numCourses, prerequisites):
    adj = defaultdict(list)
    indeg = [0] * numCourses
    for course, prereq in prerequisites:      # take prereq BEFORE course
        adj[prereq].append(course)            # edge prereq -> course
        indeg[course] += 1
 
    q = deque(c for c in range(numCourses) if indeg[c] == 0)
    taken = 0
    while q:
        c = q.popleft()
        taken += 1
        for nxt in adj[c]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
 
    return taken == numCourses

Note that I do not even build the order list here — the count is sufficient. When the follow-up asks for the actual schedule (Course Schedule II), swap taken += 1 for order.append(c) and return order if len(order) == numCourses else []. Same algorithm, two lines different. Say that out loud; it shows you see the family rather than two separate problems.

Trace on numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]. Edges: 0→1, 0→2, 1→3, 2→3. In-degrees: [0, 1, 1, 2]. Queue starts [0]. Pop 0, taken=1, decrement 1 and 2 to zero, push both. Pop 1, taken=2, decrement 3 to 1. Pop 2, taken=3, decrement 3 to 0, push. Pop 3, taken=4. Queue empty, taken == 4, return True.

Now break it. Add [0,3], making 3→0. In-degrees become [1, 1, 1, 2] and nothing starts at zero. Queue is empty immediately, taken = 0 < 4, return False. The cycle detection required no extra code at all.

For the lexicographically smallest order, build a list of zero-in-degree nodes and call heapq.heapify(q). Then use heapq.heappop(q) instead of q.popleft() and heapq.heappush(q, x) instead of q.append(x); heapq functions operate on a list, not a deque. The correctness argument is unchanged — any zero-in-degree node is legal to emit, so choosing the smallest one greedily at each step yields the lexicographically smallest valid order. Complexity goes from O(V + E) to O(V log V + E).

Solo timed

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

• Course Schedule II — return the actual order, or an empty array if impossible. The change from Course Schedule is two lines; make sure you can state which two before you start typing.
• Alien Dictionary — given words sorted in an unknown alphabet, derive the letter order. Two things to think about before coding: how do you extract a precedence edge from a pair of adjacent words, and what is the invalid case where one word is a prefix of an earlier word.

If both land early, do Minimum Height Trees. It is a topological-style peeling of leaves in an undirected tree — a good stress test of whether you understand why in-degree peeling works, since the direction argument does not apply and you peel degree-1 nodes instead.

Common failure modes

Reversing the edge direction. [a, b] with "b before a" is the edge b→a. Building a→b gives a valid topological order of the wrong graph. No crash, plausible-looking output, wrong answer. Write the direction on paper first.

Incrementing the wrong in-degree. indeg[v] += 1 where v is the dependent, not the prerequisite. The prerequisite is the source and its in-degree is untouched by this edge.

Counting duplicate edges inconsistently. If adjacency retains two copies of an edge, in-degree must count both; if you deduplicate, do so in both places. == 0 and <= 0 are equivalent with balanced counts. Neither compensates for a representation mismatch.

Using one visited bit to decide whether a revisit is a cycle. Treating every revisit as a cycle rejects a diamond DAG; ignoring every revisit misses actual cycles. Track in-progress separately from finished, using three colours or equivalent visited/active sets.

Forgetting the prefix case in Alien Dictionary. If ["abc", "ab"] appears in that order, no alphabet is consistent, because a prefix must sort first. There is no edge to extract, so a naive implementation returns a valid-looking order for an impossible input.

Not handling isolated nodes. A course with no prerequisites and no dependents has in-degree zero and belongs in the initial queue. Building the queue by iterating over the edge list rather than range(n) silently drops them, and the count check then reports a false cycle.

Myth: Cycle detection needs its own algorithm — I should run a separate check before attempting the ordering.

Why: The ordering IS the check. In Kahn's algorithm, a node inside a cycle can never reach in-degree zero, because at least one of its cycle-mates is always ahead of it and never gets emitted. So the set of nodes you failed to emit is precisely the set that is in or downstream of a cycle. Comparing the emitted count against n is a complete cycle test at zero extra cost. Writing a separate DFS cycle check first doubles your code and doubles the places a bug can hide.

Steps 1: Because a valid ordering must place every node after all of its prerequisites, a node is legal to emit exactly when its unsatisfied-prerequisite count reaches zero.

Steps 2: Because emitting a node satisfies exactly one prerequisite for each of its direct successors, the update is a single decrement per outgoing edge.

Steps 3: Because each node is enqueued at most once — initially or when its count transitions to zero — and each emitted node’s outgoing edge triggers one decrement, the total work is O(V + E).

Steps 4: Because every node in a directed cycle has at least one predecessor inside the same cycle, no member of a cycle can ever reach in-degree zero.

Steps 5: Therefore the emitted count is n if and only if the graph is acyclic — and the testable prediction is that adding v→u creates a cycle exactly when a path u→…→v already exists (including the zero-length path when u=v). With two isolated vertices, adding 1→0 changes the order but leaves the graph acyclic; with 0→1 present, it creates a cycle.

Picture: A pile of tasks, each with a count of unmet blockers written on it. You repeatedly take any task showing zero, do it, and cross one blocker off every task it was blocking. Tasks that block each other in a ring never reach zero, so they sit in the pile forever — and the leftover pile contains the ring plus any tasks blocked downstream of it.

Trigger: Fires on the words prerequisite, dependency, must come before, or 'is it possible to complete all' — anywhere a directed constraint set needs a linear order.

Name: Kahn (BFS, in-degree)

Gain: Iterative so no stack-depth limit; cycle detection falls out of the emitted count; trivially extends to lexicographic order via a heap; produces the order forward

Cost: Requires an explicit in-degree array, so one extra O(V) structure and one extra pass over the edges

Name: DFS post-order

Gain: No in-degree array; naturally gives a reverse post-order; sometimes shorter to write

Cost: Needs three-colour state to detect cycles correctly; recursion depth equals the longest chain and can exceed Python's limit; output must be reversed at the end, which is easy to forget

Pick: Kahn whenever the problem also asks whether an ordering exists, or when it may ask for the lexicographically smallest order — which covers Course Schedule, Course Schedule II and Alien Dictionary. The three-colour DFS above also handles cycles correctly; choose it when recursive depth is safe and its traversal fits the surrounding task.

Complexity

Time: O(V + E). Building the adjacency list and in-degree array is one pass over the edges, O(E). Seeding the queue scans all nodes, O(V). In the main loop each node is dequeued at most once, and its adjacency list is walked once if it is emitted. A DAG emits all nodes; a cyclic graph may leave nodes and outgoing edges unprocessed. Total O(V + E).

The lexicographic variant with a heap is O(V log V + E) — the log factor comes from up to V pushes and V pops on the heap.

Space: O(V + E). The adjacency list is O(V + E), the in-degree array is O(V), and the queue holds at most V entries. For the DFS form, the recursion stack adds O(V) in the worst case, which is a chain graph.

For the lowercase-English-letter Alien Dictionary contract, V is at most 26; a different alphabet changes that bound. Each adjacent word pair contributes at most one precedence edge, so E is at most the number of pairs before deduplication. The real cost is the O(total characters) scan to extract the edges.

Self-check (answer follows each question).

Q: In Kahn's algorithm, what does it mean when the emitted order has fewer than n nodes?

A: The graph contains at least one directed cycle. Every node in a cycle keeps at least one unsatisfied prerequisite forever, so it never reaches in-degree zero and is never emitted.

Q: Given prerequisites = [[a, b]] meaning take b before a, which in-degree do you increment and which adjacency entry do you append?

A: The edge is b → a. Append a to adj[b], and increment indeg[a]. The prerequisite is the source; the dependent gains the incoming edge.

Q: Why does DFS-based cycle detection need three states rather than a simple visited set?

A: Two states cannot distinguish 'currently on the recursion stack' from 'fully finished'. A diamond DAG revisits a finished node legitimately; only a revisit to an in-progress (grey) node is a back edge and therefore a cycle.

Q: How do you change Kahn's algorithm to return the lexicographically smallest valid ordering, and what does it cost?

A: Initialize a list of zero-in-degree vertices and heapify it. Use heappush for newly ready vertices and heappop to select the smallest. Cost is O(V log V + E); the smallest legal next vertex gives the lexicographically smallest valid prefix.

Q: Why must the initial queue be built by scanning range(n) rather than by scanning the edge list?

A: Isolated nodes appear in no edge but still have in-degree zero and must be emitted. Building from the edge list drops them, and the final count check then falsely reports a cycle.

Q: In Alien Dictionary, what precedence edge do you extract from two adjacent words, and which input makes the problem unsolvable regardless of the graph?

A: Compare the two words character by character and take the FIRST position where they differ: that gives one edge, earlier letter before later letter, and you stop there — subsequent differences carry no information. If no differing position exists and the first word is longer than the second, the input is invalid, because a prefix must sort before the longer word.

Stretch: true

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

Course Schedule enters the queue today. If you had to run the sample input to work out which way the edge pointed, log it hint at best — the direction should come from reading the sentence, not from experiment.

• In-degree is the count of unmet prerequisites. A node becomes legal the instant it hits zero, and that is the entire algorithm.

• The cycle detector is free: emit fewer than n nodes and the graph has a cycle. Never write a separate cycle check before a topological sort.

• Edge direction is the killer bug. 'Take b before a' is the edge b → a, so indeg[a] increments. Reversing it produces a valid order of the wrong graph.

• Course Schedule and Course Schedule II differ by two lines. Recognise the family, not the individual problem.

• Lexicographically smallest order = swap the deque for a min-heap. Correctness argument unchanged, cost becomes O(V log V + E).

• DFS cycle detection must distinguish active from finished nodes. Treating every visited node as active falsely flags a diamond DAG.

Corrective source notes

• CPython 3.14.0 heapq documentation — list-backed heap initialization and minimum extraction; read fresh 2026-10-09.
• Topological Sorting - Algorithms for Competitive Programming — A topological order places each directed predecessor before its successor and exists for a DAG. 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.