Course Schedule II: topological sort finally returns the order

Problem 207 asked a yes/no question: can you finish all courses? This one asks for the receipt. Return an actual ordering, or an empty array if a cycle makes it impossible. That is a meaningful shift — cycle detection was enough before; now you need a valid topological order of the entire graph.

The good news: both algorithms from 207 extend naturally. The DFS three-color approach collects nodes in post-order and reverses at the end. Kahn's BFS approach already builds the order as it goes. Neither requires rethinking from scratch.

The problem

Given numCourses courses labeled 0 to numCourses - 1 and a list of prerequisite pairs where [a, b] means you must take course b before course a, return a valid ordering of all courses to finish them all — or an empty array if a cycle makes it impossible. Full statement: LeetCode 210.

Constraints:
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= numCourses * (numCourses - 1)
- prerequisites[i].length == 2
- 0 <= ai, bi < numCourses
- ai != bi
- All the pairs [ai, bi] are distinct.

Reading the constraints before touching the code

1 <= numCourses <= 2000. Same as 207 — every course fits in an array indexed by course number. No hash map for the graph; plain arrays work. The vertex count also tells you that O(V²) is borderline acceptable (4M ops), but we can do O(V+E) and there is no reason not to.

0 <= prerequisites.length <= numCourses * (numCourses - 1). The edge count can be as high as 2000 * 1999 = ~4M, which is a dense graph. In the dense case, adjacency list representation takes the same space as an adjacency matrix, but the algorithms are still O(V+E) either way. In the typical sparse case this is much better.

ai != bi — no self-loops. A course cannot be its own prerequisite, so you never need to handle the degenerate self-cycle case.

All pairs are distinct — no duplicate edges. Construction is straightforward; no deduplication pass needed.

The direction convention: [a, b] means take b before a. Edge goes b -> a. I still draw a small picture when building the graph because getting the direction backwards is the most common bug on this problem.

With numCourses <= 2000, even an O(V+E) algorithm with a large constant factor is fine. What you want to avoid is an O(V²) outer loop searching for unvisited nodes inside an already-O(E) inner loop — that would push you to O(V² + E) unnecessarily. The standard implementations below are all clean O(V+E).

DFS with three-color marking and post-order collection

The idea: run DFS on every unvisited node. When you enter a node, mark it GRAY (in progress). When you finish all its descendants, mark it BLACK (done) and append it to the result. If you ever enter a node that is already GRAY, you have found a back edge — a cycle — and the answer is empty.

Why does appending at the BLACK step give a topological order? A node gets marked BLACK only after every course that depends on it has already been processed. So if course A must come before course B, B will be finished and appended before A. That means the result list has A before B in reverse — which is why you reverse at the end.

from typing import List
 
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(numCourses)]
        for course, prereq in prerequisites:
            graph[prereq].append(course)
 
        WHITE, GRAY, BLACK = 0, 1, 2
        color = [WHITE] * numCourses
        result = []
        has_cycle = False
 
        def dfs(node: int) -> None:
            nonlocal has_cycle
            if color[node] == GRAY:
                has_cycle = True
                return
            if color[node] == BLACK:
                return
 
            color[node] = GRAY
            for neighbor in graph[node]:
                dfs(neighbor)
                if has_cycle:
                    return
 
            color[node] = BLACK
            result.append(node)
 
        for i in range(numCourses):
            if color[i] == WHITE:
                dfs(i)
                if has_cycle:
                    return []
 
        return result[::-1]

public class Solution {
    private const int WHITE = 0, GRAY = 1, BLACK = 2;
    private bool hasCycle = false;
 
    public int[] FindOrder(int numCourses, int[][] prerequisites) {
        List<int>[] graph = new List<int>[numCourses];
        for (int i = 0; i < numCourses; i++)
            graph[i] = new List<int>();
 
        foreach (var prereq in prerequisites)
            graph[prereq[1]].Add(prereq[0]);
 
        int[] color = new int[numCourses];
        var result = new List<int>();
 
        for (int i = 0; i < numCourses; i++) {
            if (color[i] == WHITE) {
                Dfs(i, graph, color, result);
                if (hasCycle) return new int[0];
            }
        }
 
        result.Reverse();
        return result.ToArray();
    }
 
    private void Dfs(int node, List<int>[] graph, int[] color, List<int> result) {
        if (color[node] == GRAY) { hasCycle = true; return; }
        if (color[node] == BLACK) return;
 
        color[node] = GRAY;
        foreach (int neighbor in graph[node]) {
            Dfs(neighbor, graph, color, result);
            if (hasCycle) return;
        }
 
        color[node] = BLACK;
        result.Add(node);
    }
}

Hand trace: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

The graph as built (direction: prereq -> course):

Start DFS from node 0 (WHITE):

color[0] = GRAY
  neighbor 1: color[1] = GRAY
    neighbor 3: color[3] = GRAY
      no neighbors
    color[3] = BLACK, result = [3]
  color[1] = BLACK, result = [3, 1]
  neighbor 2: color[2] = GRAY
    neighbor 3: color[3] == BLACK -> return immediately
  color[2] = BLACK, result = [3, 1, 2]
color[0] = BLACK, result = [3, 1, 2, 0]

Reverse -> [0, 2, 1, 3]

Node 3 gets appended first because it has no outgoing edges — nothing depends on it later in the chain, but everything in this example eventually leads to it. Reversing puts the root (0, no prerequisites) at the front. The final order [0, 2, 1, 3] is valid: course 3 requires both 1 and 2, and both require 0, so 0 must come first.

Complexity

Time: O(V+E). Every node is visited exactly once (WHITE -> GRAY -> BLACK). Every edge is traversed exactly once from the GRAY state of its source.

Space: O(V+E). The adjacency list takes O(E). The color array takes O(V). The call stack depth is at most O(V) in the worst case (a linear chain). Result list is O(V).

Kahn's algorithm: BFS from in-degree zero

Kahn's flips the perspective. Instead of going deep into dependencies, you start from courses with no prerequisites and peel them off layer by layer. An in-degree counter tracks how many remaining prerequisites each course has. When that counter hits zero, the course is ready to take.

No in-degree-zero node left but some courses remain? That means those remaining courses are all involved in a cycle — they all have at least one outstanding dependency, and those dependencies point back to them. In that case, result.length < numCourses and you return empty.

Crucially, Kahn's produces the topological order directly — no reversal needed. You add each node to the result the moment it becomes available.

from collections import deque
from typing import List
 
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(numCourses)]
        in_degree = [0] * numCourses
 
        for course, prereq in prerequisites:
            graph[prereq].append(course)
            in_degree[course] += 1
 
        queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
        result = []
 
        while queue:
            current = queue.popleft()
            result.append(current)
            for neighbor in graph[current]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
 
        return result if len(result) == numCourses else []

public class Solution {
    public int[] FindOrder(int numCourses, int[][] prerequisites) {
        var graph = new List<int>[numCourses];
        int[] inDegree = new int[numCourses];
 
        for (int i = 0; i < numCourses; i++)
            graph[i] = new List<int>();
 
        foreach (var prereq in prerequisites) {
            graph[prereq[1]].Add(prereq[0]);
            inDegree[prereq[0]]++;
        }
 
        var queue = new Queue<int>();
        for (int i = 0; i < numCourses; i++)
            if (inDegree[i] == 0) queue.Enqueue(i);
 
        var result = new List<int>();
 
        while (queue.Count > 0) {
            int current = queue.Dequeue();
            result.Add(current);
            foreach (int neighbor in graph[current]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) queue.Enqueue(neighbor);
            }
        }
 
        return result.Count == numCourses ? result.ToArray() : new int[0];
    }
}

Hand trace: same example

numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

graph:     0->[1,2], 1->[3], 2->[3], 3->[]
in_degree: [0, 1, 1, 2]

queue = [0]  (only node with in_degree 0)
result = []

Step 1: dequeue 0 -> result = [0]
  neighbor 1: in_degree[1] = 1-1 = 0 -> enqueue 1
  neighbor 2: in_degree[2] = 1-1 = 0 -> enqueue 2
  queue = [1, 2]

Step 2: dequeue 1 -> result = [0, 1]
  neighbor 3: in_degree[3] = 2-1 = 1 -> not yet ready
  queue = [2]

Step 3: dequeue 2 -> result = [0, 1, 2]
  neighbor 3: in_degree[3] = 1-1 = 0 -> enqueue 3
  queue = [3]

Step 4: dequeue 3 -> result = [0, 1, 2, 3]
  no neighbors
  queue = []

len(result) == 4 == numCourses -> return [0, 1, 2, 3]

No reversal. The order emerges naturally: you cannot process a node until all its prerequisites are done, and you process it the moment they are.

Complexity

Time: O(V+E). Each node enters and leaves the queue exactly once. Each edge is traversed exactly once when decrementing in-degree.

Space: O(V+E). Adjacency list O(E), in-degree array O(V), queue at most O(V), result O(V).

Edge cases that matter

No prerequisites (prerequisites = []): in-degree is zero for every node. Kahn's enqueues all numCourses nodes immediately and drains them in 0..numCourses-1 order. DFS visits every node individually, appends them in visit order, reverses. Both return a valid (though arbitrary) ordering.

Single course (numCourses = 1, prerequisites = []): both approaches return [0] immediately. Kahn's puts 0 in the queue, dequeues it, result length equals 1. DFS runs from 0, no neighbors, appends 0, reverses to [0].

Cycle present (e.g., prerequisites = [[0,1],[1,0]]): Kahn's never enqueues either node — both have in-degree 1 and neither drops to 0. result.length = 0 != 2, returns []. DFS enters node 0, marks GRAY, enters node 1, marks GRAY, then sees 0 is GRAY and sets has_cycle = True, unwinds and returns []. Same outcome, different detection mechanism.

Disconnected graph: if courses form multiple independent components with no edges between them, both algorithms handle this correctly. DFS's outer loop covers all WHITE nodes regardless of connectivity. Kahn's enqueues every zero-in-degree node at the start, covering all components.

Maximum density (prerequisites.length = numCourses * (numCourses - 1)): this is a complete directed graph. If it has a cycle, both return [] quickly. If somehow it is acyclic (which requires a strict total order), both will process all edges. The O(V+E) bound still holds; it just means E is large.

Comparison table

Same asymptotic cost, meaningfully different structure.

Which one I'd actually ship

Kahn's. Every time, without much deliberation.

The reasons are practical. Kahn's produces the result in the correct order without a final reversal step — that reversal in DFS is a source of bugs that are hard to catch in testing because the test cases usually accept any valid order. Kahn's also uses an explicit queue instead of recursion, which means you do not risk hitting Python's default recursion limit on large inputs (Python's limit is 1000 by default; with numCourses = 2000 and a degenerate linear chain, DFS would exceed it). The C# version avoids that issue, but in Python it is a real concern.

The DFS version is worth understanding because three-color cycle detection is a standalone technique you will use again — it appears in problems involving detecting back edges in general directed graphs. But for this specific problem, where you just need a valid topological order, Kahn's is cleaner and less error-prone.

The underlying pattern: topological sort on a DAG

Both approaches are instances of the same conceptual pattern: linearize a directed acyclic graph so that every edge u -> v has u before v in the output. This pattern appears wherever there are dependencies — build systems resolving compilation order, package managers resolving install order, task schedulers enforcing precedence constraints.

The two canonical implementations of topological sort map to the two classic graph traversals: post-order DFS (collect after finishing all descendants, reverse at the end) and BFS by in-degree (Kahn's). Every topological sort problem you encounter will be a variation on one of these two.

The cycle check is not separate from the topological sort — it is intrinsic. A topological order exists if and only if the graph is a DAG. The moment you attempt topological sort and hit a GRAY node (DFS) or exhaust the queue with uncounted nodes remaining (Kahn's), you know the DAG property fails.

Where this fits and what comes next

In the graphs series, this is the third topological sort problem in a cluster. Course Schedule (207) introduced the cycle-detection question. This problem (210) adds the requirement to return the actual order. The technique is the same; the output contract is stricter.

Course Schedule (207) is the direct predecessor. If 207 felt comfortable, this adds exactly one thing: storing and reversing the DFS output, or reading off Kahn's result directly. The extra work is minimal.

Alien Dictionary (LeetCode 269) is the natural escalation. You are given a list of words sorted according to an alien alphabet; you must reconstruct the ordering of characters. The problem is still topological sort on a DAG — you build edges from adjacent words that share a differing character — but now you have to construct the graph from scratch rather than being handed the edge list. The same Kahn's pattern applies.

Sequence Reconstruction (LeetCode 444) asks whether a given sequence is the unique shortest supersequence from which all provided subsequences can be reconstructed — which is equivalent to asking whether there is a unique topological order. It forces you to think about when in-degree-zero ambiguity means multiple valid orderings exist.

Parallel Courses (LeetCode 1136) adds a twist: courses at the same level (in the same BFS wave in Kahn's) can be taken in parallel. The answer is the number of BFS waves — the length of the critical path through the DAG. This is a direct extension of Kahn's algorithm where you track wave depth instead of just collecting order.