Topological Sort

Order the nodes of a directed graph so every edge points forward, or prove a cycle makes that impossible, using in-degree counts or DFS.

IntermediateRead first: Graphs: BFS & DFS

How It Works

A topological order lists the nodes of a directed graph so that every edge points forward: for each edge u -> v, u comes before v. Edges usually mean "has to happen first": a course before the course that requires it, a package before the packages that import it, a spreadsheet cell before the cells whose formulas read it. Most graphs allow several valid orders, and you usually only need one.

An order exists exactly when the graph has no directed cycle, which is what a DAG (directed acyclic graph) is. If a has to come before b and b before a, nothing works. So every topological sort doubles as a cycle detector, and many problems only ask that question: can all of this be done at all?

  0 ----> 1 ----> 3 ----> 4
  |               ^       ^
  |               |       |
  +-----> 2 ------+       5

  one valid order:  [0, 5, 1, 2, 3, 4]
  another:          [5, 0, 2, 1, 3, 4]

Node 3 needs both 1 and 2, and 4 needs both 3 and 5. Nodes 0 and 5 need nothing, so either can go first.

Kahn's algorithm builds the order from the front. Count each node's in-degree, the number of edges pointing at it. A node with in-degree 0 has nothing left to wait for, so it can go next. Place it, then delete its outgoing edges by lowering each neighbor's in-degree. Any neighbor that drops to 0 is now free. Repeat until no free node is left. If some nodes never come out, each one still has an incoming edge from another leftover node. Follow those edges backwards and you must eventually revisit a node, because there are only finitely many: that's the cycle.

Kahn's Algorithm, Step by Step

Step 1 of 9

graph

queue

Just placed, and the edges it spends
In-degree 0, waiting in the queue
Placed in the order
Spent edge

Count each node's in-degree, the number of edges pointing at it. 3 and 4 start at 2, because each one waits on two other nodes.

0 and 5 have in-degree 0, so nothing has to come before them. They seed the queue, in ascending order.

Pop 0 and append it to order, which always matches the queue up to head. Spending its edges drops 1 to 0 and 2 to 0. Neither waits on anything now, so both join the queue.

Pop 5 and append it to order. Spending its edge drops 4 to 1. 4 still waits on 3, so it stays out of the queue.

Pop 1 and append it to order. Spending its edge drops 3 to 1. 3 still waits on 2, so it stays out of the queue.

Pop 2 and append it to order. Spending its edge drops 3 to 0. 2 was its last prerequisite, so 3 joins the queue.

Pop 3 and append it to order. Spending its edge drops 4 to 0. 3 was its last prerequisite, so 4 joins the queue.

Pop 4 and append it to order. It points at nothing, so there are no edges to spend.

The queue is empty and order holds all 6 nodes, so there's no cycle. Every edge points forward in [0, 5, 1, 2, 3, 4].

All 9 steps as text

Count each node's in-degree, the number of edges pointing at it. 3 and 4 start at 2, because each one waits on two other nodes.
0 and 5 have in-degree 0, so nothing has to come before them. They seed the queue, in ascending order.
Pop 0 and append it to order, which always matches the queue up to head. Spending its edges drops 1 to 0 and 2 to 0. Neither waits on anything now, so both join the queue.
Pop 5 and append it to order. Spending its edge drops 4 to 1. 4 still waits on 3, so it stays out of the queue.
Pop 1 and append it to order. Spending its edge drops 3 to 1. 3 still waits on 2, so it stays out of the queue.
Pop 2 and append it to order. Spending its edge drops 3 to 0. 2 was its last prerequisite, so 3 joins the queue.
Pop 3 and append it to order. Spending its edge drops 4 to 0. 3 was its last prerequisite, so 4 joins the queue.
Pop 4 and append it to order. It points at nothing, so there are no edges to spend.
The queue is empty and order holds all 6 nodes, so there's no cycle. Every edge points forward in [0, 5, 1, 2, 3, 4].

The other approach is DFS. Run a DFS from every unvisited node and append each node to a list once everything it points to is finished (post-order). Reversing that list gives a topological order, because a node always finishes after all the nodes it points to. To detect cycles, track three states per node: unvisited, on the current path, and done. Reaching a node that's still on the current path means you've found a cycle. Course Schedule below uses those three states to find a cycle.

When to Reach for It

Tasks, courses or build steps come with prerequisites: "X has to happen before Y".
You need any order that respects a set of dependencies, or to report that none exists.
The question asks whether a directed graph has a cycle, or whether a set of requirements can all be met.
You need the earliest finish time or the longest path in a DAG. Process nodes in topological order and carry the best value forward along each edge.
An order has to be inferred from pairwise comparisons, such as the letter order of an alien alphabet from a sorted word list.

Complexity

Operation	Time	Space
Kahn's algorithm	O(V + E)	O(V + E)
DFS post-order, reversed	O(V + E)	O(V + E), with recursion up to V deep
Cycle check (either method)	O(V + E)	O(V + E)
Smallest order by label (min-heap instead of a queue)	O(V log V + E)	O(V + E)

The Template

Kahn's Algorithm

One pass over the edges builds the adjacency list and counts in-degrees. Seed a first-in, first-out queue with every node whose in-degree is 0, scanning the nodes in ascending order. Then pop a node, append it to the order, and decrement the in-degree of each node it points to. A node joins the queue at the moment its count hits 0, which is the moment its last prerequisite is placed.

in-degree  0:0  1:1  2:1  3:2  4:2  5:0

start   queue [0, 5]
pop 0   queue [5, 1, 2]   1 and 2 drop to 0
pop 5   queue [1, 2]      4 drops to 1
pop 1   queue [2]         3 drops to 1
pop 2   queue [3]         3 drops to 0
pop 3   queue [4]         4 drops to 0
pop 4   queue []

order [0, 5, 1, 2, 3, 4]

Kahn's algorithm on the graph above. Node 3 joins the queue only once both 1 and 2 are placed.

If the order ends up shorter than n, some nodes never reached in-degree 0, because they sit on a cycle or wait on a node that does. The function returns [] in that case. The second demo shows it: node 0 comes out, but 1, 2 and 3 form a loop and stay stuck at in-degree 1.

Time O(V + E)Space O(V + E)

from collections import deque


def topological_sort(n: int, edges: list[list[int]]) -> list[int]:
    """A topological order of nodes 0..n-1, where each edge [u, v] means u must
    come before v. Returns [] if a cycle makes that impossible."""
    graph: list[list[int]] = [[] for _ in range(n)]
    in_degree = [0] * n  # Edges still pointing at each node.
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    # Seed with every node that waits on nothing, in ascending order.
    queue = deque(node for node in range(n) if in_degree[node] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1  # node is placed, so neighbor waits on one less.
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    # A node on a cycle never reaches in-degree 0, so it never comes out.
    return order if len(order) == n else []


if __name__ == "__main__":
    print(topological_sort(6, [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [5, 4]]))  # [0, 5, 1, 2, 3, 4]
    print(topological_sort(4, [[0, 1], [1, 2], [2, 3], [3, 1]]))  # []
    print(topological_sort(3, []))  # [0, 1, 2]

// A topological order of nodes 0..n-1, where each edge [u, v] means u must
// come before v. Returns [] if a cycle makes that impossible.
export function topologicalSort(n: number, edges: number[][]): number[] {
  const graph: number[][] = Array.from({ length: n }, () => []);
  const inDegree = new Array<number>(n).fill(0); // Edges still pointing at each node.
  for (const [u, v] of edges) {
    graph[u].push(v);
    inDegree[v]++;
  }
  // Seed with every node that waits on nothing, in ascending order.
  const queue: number[] = [];
  for (let node = 0; node < n; node++) {
    if (inDegree[node] === 0) queue.push(node);
  }
  const order: number[] = [];
  let head = 0; // Dequeue by moving a head index, because shift() is O(n).
  while (head < queue.length) {
    const node = queue[head++];
    order.push(node);
    for (const neighbor of graph[node]) {
      inDegree[neighbor]--; // node is placed, so neighbor waits on one less.
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  // A node on a cycle never reaches in-degree 0, so it never comes out.
  return order.length === n ? order : [];
}

console.log(JSON.stringify(topologicalSort(6, [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [5, 4]]))); // [0,5,1,2,3,4]
console.log(JSON.stringify(topologicalSort(4, [[0, 1], [1, 2], [2, 3], [3, 1]]))); // []
console.log(JSON.stringify(topologicalSort(3, []))); // [0,1,2]

package main

import "fmt"

// topologicalSort returns a topological order of nodes 0..n-1, where each
// edge [u, v] means u must come before v. It returns [] if a cycle makes that
// impossible.
func topologicalSort(n int, edges [][]int) []int {
	graph := make([][]int, n)
	inDegree := make([]int, n) // Edges still pointing at each node.
	for _, e := range edges {
		u, v := e[0], e[1]
		graph[u] = append(graph[u], v)
		inDegree[v]++
	}
	// Seed with every node that waits on nothing, in ascending order.
	queue := []int{}
	for node := 0; node < n; node++ {
		if inDegree[node] == 0 {
			queue = append(queue, node)
		}
	}
	order := []int{}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		order = append(order, node)
		for _, neighbor := range graph[node] {
			inDegree[neighbor]-- // node is placed, so neighbor waits on one less.
			if inDegree[neighbor] == 0 {
				queue = append(queue, neighbor)
			}
		}
	}
	// A node on a cycle never reaches in-degree 0, so it never comes out.
	if len(order) < n {
		return []int{}
	}
	return order
}

func main() {
	fmt.Println(topologicalSort(6, [][]int{{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {5, 4}})) // [0 5 1 2 3 4]
	fmt.Println(topologicalSort(4, [][]int{{0, 1}, {1, 2}, {2, 3}, {3, 1}}))                 // []
	fmt.Println(topologicalSort(3, [][]int{}))                                               // [0 1 2]
}

using System;
using System.Collections.Generic;

public class Solution
{
    // A topological order of nodes 0..n-1, where each edge [u, v] means u must
    // come before v. Returns [] if a cycle makes that impossible.
    public static List<int> TopologicalSort(int n, int[][] edges)
    {
        var graph = new List<List<int>>();
        for (int i = 0; i < n; i++) graph.Add(new List<int>());
        var inDegree = new int[n]; // Edges still pointing at each node.
        foreach (var edge in edges)
        {
            int u = edge[0], v = edge[1];
            graph[u].Add(v);
            inDegree[v]++;
        }
        // Seed with every node that waits on nothing, in ascending order.
        var queue = new Queue<int>();
        for (int node = 0; node < n; node++)
        {
            if (inDegree[node] == 0) queue.Enqueue(node);
        }
        var order = new List<int>();
        while (queue.Count > 0)
        {
            int node = queue.Dequeue();
            order.Add(node);
            foreach (int neighbor in graph[node])
            {
                inDegree[neighbor]--; // node is placed, so neighbor waits on one less.
                if (inDegree[neighbor] == 0) queue.Enqueue(neighbor);
            }
        }
        // A node on a cycle never reaches in-degree 0, so it never comes out.
        return order.Count == n ? order : new List<int>();
    }

    public static void Main()
    {
        Console.WriteLine(Format(TopologicalSort(6, [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [5, 4]]))); // [0, 5, 1, 2, 3, 4]
        Console.WriteLine(Format(TopologicalSort(4, [[0, 1], [1, 2], [2, 3], [3, 1]]))); // []
        Console.WriteLine(Format(TopologicalSort(3, []))); // [0, 1, 2]
    }

    static string Format(List<int> values) => "[" + string.Join(", ", values) + "]";
}

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

public class Solution {
    // A topological order of nodes 0..n-1, where each edge [u, v] means u must
    // come before v. Returns [] if a cycle makes that impossible.
    static List<Integer> topologicalSort(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        int[] inDegree = new int[n]; // Edges still pointing at each node.
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            graph.get(u).add(v);
            inDegree[v]++;
        }
        // Seed with every node that waits on nothing, in ascending order.
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        for (int node = 0; node < n; node++) {
            if (inDegree[node] == 0) queue.add(node);
        }
        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order.add(node);
            for (int neighbor : graph.get(node)) {
                inDegree[neighbor]--; // node is placed, so neighbor waits on one less.
                if (inDegree[neighbor] == 0) queue.add(neighbor);
            }
        }
        // A node on a cycle never reaches in-degree 0, so it never comes out.
        return order.size() == n ? order : List.of();
    }

    public static void main(String[] args) {
        System.out.println(topologicalSort(6, new int[][] {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {5, 4}})); // [0, 5, 1, 2, 3, 4]
        System.out.println(topologicalSort(4, new int[][] {{0, 1}, {1, 2}, {2, 3}, {3, 1}})); // []
        System.out.println(topologicalSort(3, new int[][] {})); // [0, 1, 2]
    }
}

Worked Problems

Each solution stays folded until you open it, so you can try the problem first. Every one is a complete program in Python, TypeScript, Go, C# and Java, run and checked against its expected output.

Course Schedule

MEDIUMLeetCode 207

Problem

There are numCourses courses labeled 0 to numCourses - 1. Each pair [a, b] in prerequisites says you have to finish course b before you can take course a. Return whether it's possible to finish every course.

Example: with 2 courses and [[1, 0], [0, 1]], the answer is false. Course 1 needs course 0 and course 0 needs course 1, so neither can go first. With just [[1, 0]], the answer is true: take 0, then 1.

Show Solution

Approach

Draw the edge b -> a for each pair, since b comes first. Every course can be finished exactly when this graph has no cycle, so the problem is pure cycle detection. Kahn's algorithm would work (check whether every course comes out). This solution shows the other method: a DFS that gives each node one of three states, often called white, gray and black.

UNVISITED (white): the DFS hasn't reached it yet.
VISITING (gray): it's on the current path, somewhere between where this search started and the node being explored right now.
DONE (black): it and everything reachable from it have been explored, and no cycle turned up.

An edge into a VISITING node leads back into the current path, so the path plus that edge is a cycle. An edge into a DONE node is safe to skip. This is why one seen flag isn't enough in a directed graph. In the third demo, course 3 is reached through both 1 and 2. On the second arrival it's DONE, not on the path, so there's no cycle. A plain seen flag can't tell those two cases apart and would report a false cycle.

Because a DONE node is never searched again, each of the V courses and E prerequisite pairs is handled once. The outer loop starts a search from every unvisited course, because a cycle can sit where earlier searches never reached. In the last demo, the search from course 0 only sees 0 and 1, and the loop between 2 and 3 turns up when the outer loop gets to course 2. The recursion can go as deep as the longest prerequisite chain, so for very long chains in Python, raise the recursion limit or use Kahn's.

Time O(V + E)Space O(V + E)

UNVISITED = 0
VISITING = 1  # On the current DFS path.
DONE = 2  # Fully explored, and no cycle runs through it.


def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    """Whether every course can be taken, given pairs [course, pre] meaning
    pre must be taken before course. False exactly when there's a cycle."""
    graph: list[list[int]] = [[] for _ in range(num_courses)]
    for course, pre in prerequisites:
        graph[pre].append(course)
    state = [UNVISITED] * num_courses
    # Start from every course: a cycle can hide where no earlier search reached.
    for node in range(num_courses):
        if state[node] == UNVISITED and has_cycle(graph, node, state):
            return False
    return True


def has_cycle(graph: list[list[int]], node: int, state: list[int]) -> bool:
    state[node] = VISITING
    for neighbor in graph[node]:
        if state[neighbor] == VISITING:
            return True  # Back to a node on this path: a cycle.
        if state[neighbor] == UNVISITED and has_cycle(graph, neighbor, state):
            return True
    state[node] = DONE  # Nothing below leads back here, so never search it again.
    return False


if __name__ == "__main__":
    print(can_finish(2, [[1, 0]]))  # True
    print(can_finish(2, [[1, 0], [0, 1]]))  # False
    print(can_finish(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))  # True
    print(can_finish(4, [[1, 0], [2, 3], [3, 2]]))  # False

const UNVISITED = 0;
const VISITING = 1; // On the current DFS path.
const DONE = 2; // Fully explored, and no cycle runs through it.

// Whether every course can be taken, given pairs [course, pre] meaning
// pre must be taken before course. False exactly when there's a cycle.
export function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const graph: number[][] = Array.from({ length: numCourses }, () => []);
  for (const [course, pre] of prerequisites) graph[pre].push(course);
  const state = new Array<number>(numCourses).fill(UNVISITED);
  // Start from every course: a cycle can hide where no earlier search reached.
  for (let node = 0; node < numCourses; node++) {
    if (state[node] === UNVISITED && hasCycle(graph, node, state)) return false;
  }
  return true;
}

function hasCycle(graph: number[][], node: number, state: number[]): boolean {
  state[node] = VISITING;
  for (const neighbor of graph[node]) {
    if (state[neighbor] === VISITING) return true; // Back to a node on this path: a cycle.
    if (state[neighbor] === UNVISITED && hasCycle(graph, neighbor, state)) return true;
  }
  state[node] = DONE; // Nothing below leads back here, so never search it again.
  return false;
}

console.log(canFinish(2, [[1, 0]])); // true
console.log(canFinish(2, [[1, 0], [0, 1]])); // false
console.log(canFinish(4, [[1, 0], [2, 0], [3, 1], [3, 2]])); // true
console.log(canFinish(4, [[1, 0], [2, 3], [3, 2]])); // false

package main

import "fmt"

const (
	unvisited = iota
	visiting  // On the current DFS path.
	done      // Fully explored, and no cycle runs through it.
)

// canFinish reports whether every course can be taken, given pairs
// [course, pre] meaning pre must be taken before course. It is false exactly
// when there's a cycle.
func canFinish(numCourses int, prerequisites [][]int) bool {
	graph := make([][]int, numCourses)
	for _, p := range prerequisites {
		course, pre := p[0], p[1]
		graph[pre] = append(graph[pre], course)
	}
	state := make([]int, numCourses) // Every entry starts as unvisited.
	// Start from every course: a cycle can hide where no earlier search reached.
	for node := 0; node < numCourses; node++ {
		if state[node] == unvisited && hasCycle(graph, node, state) {
			return false
		}
	}
	return true
}

func hasCycle(graph [][]int, node int, state []int) bool {
	state[node] = visiting
	for _, neighbor := range graph[node] {
		if state[neighbor] == visiting {
			return true // Back to a node on this path: a cycle.
		}
		if state[neighbor] == unvisited && hasCycle(graph, neighbor, state) {
			return true
		}
	}
	state[node] = done // Nothing below leads back here, so never search it again.
	return false
}

func main() {
	fmt.Println(canFinish(2, [][]int{{1, 0}}))                         // true
	fmt.Println(canFinish(2, [][]int{{1, 0}, {0, 1}}))                 // false
	fmt.Println(canFinish(4, [][]int{{1, 0}, {2, 0}, {3, 1}, {3, 2}})) // true
	fmt.Println(canFinish(4, [][]int{{1, 0}, {2, 3}, {3, 2}}))         // false
}

using System;
using System.Collections.Generic;

public class Solution
{
    const int Unvisited = 0;
    const int Visiting = 1; // On the current DFS path.
    const int Done = 2; // Fully explored, and no cycle runs through it.

    // Whether every course can be taken, given pairs [course, pre] meaning
    // pre must be taken before course. False exactly when there's a cycle.
    public static bool CanFinish(int numCourses, int[][] prerequisites)
    {
        var graph = new List<List<int>>();
        for (int i = 0; i < numCourses; i++) graph.Add(new List<int>());
        foreach (var p in prerequisites)
        {
            int course = p[0], pre = p[1];
            graph[pre].Add(course);
        }
        var state = new int[numCourses]; // Every entry starts as Unvisited.
        // Start from every course: a cycle can hide where no earlier search reached.
        for (int node = 0; node < numCourses; node++)
        {
            if (state[node] == Unvisited && HasCycle(graph, node, state)) return false;
        }
        return true;
    }

    static bool HasCycle(List<List<int>> graph, int node, int[] state)
    {
        state[node] = Visiting;
        foreach (int neighbor in graph[node])
        {
            if (state[neighbor] == Visiting) return true; // Back to a node on this path: a cycle.
            if (state[neighbor] == Unvisited && HasCycle(graph, neighbor, state)) return true;
        }
        state[node] = Done; // Nothing below leads back here, so never search it again.
        return false;
    }

    public static void Main()
    {
        Console.WriteLine(CanFinish(2, [[1, 0]])); // True
        Console.WriteLine(CanFinish(2, [[1, 0], [0, 1]])); // False
        Console.WriteLine(CanFinish(4, [[1, 0], [2, 0], [3, 1], [3, 2]])); // True
        Console.WriteLine(CanFinish(4, [[1, 0], [2, 3], [3, 2]])); // False
    }
}

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

public class Solution {
    static final int UNVISITED = 0;
    static final int VISITING = 1; // On the current DFS path.
    static final int DONE = 2; // Fully explored, and no cycle runs through it.

    // Whether every course can be taken, given pairs [course, pre] meaning
    // pre must be taken before course. False exactly when there's a cycle.
    static boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        for (int[] p : prerequisites) {
            int course = p[0], pre = p[1];
            graph.get(pre).add(course);
        }
        int[] state = new int[numCourses]; // Every entry starts as UNVISITED.
        // Start from every course: a cycle can hide where no earlier search reached.
        for (int node = 0; node < numCourses; node++) {
            if (state[node] == UNVISITED && hasCycle(graph, node, state)) return false;
        }
        return true;
    }

    static boolean hasCycle(List<List<Integer>> graph, int node, int[] state) {
        state[node] = VISITING;
        for (int neighbor : graph.get(node)) {
            if (state[neighbor] == VISITING) return true; // Back to a node on this path: a cycle.
            if (state[neighbor] == UNVISITED && hasCycle(graph, neighbor, state)) return true;
        }
        state[node] = DONE; // Nothing below leads back here, so never search it again.
        return false;
    }

    public static void main(String[] args) {
        System.out.println(canFinish(2, new int[][] {{1, 0}})); // true
        System.out.println(canFinish(2, new int[][] {{1, 0}, {0, 1}})); // false
        System.out.println(canFinish(4, new int[][] {{1, 0}, {2, 0}, {3, 1}, {3, 2}})); // true
        System.out.println(canFinish(4, new int[][] {{1, 0}, {2, 3}, {3, 2}})); // false
    }
}

Course Schedule II

MEDIUMLeetCode 210

Problem

Same setup as Course Schedule: numCourses courses and pairs [a, b] meaning b has to come before a. This time, return an order in which you can take all of them. If several orders work, any one is accepted. If none does, return an empty array.

Example: with 4 courses and [[1, 0], [2, 0], [3, 1], [3, 2]], course 0 has no prerequisites, 1 and 2 each need only 0, and 3 needs both 1 and 2. Both [0, 1, 2, 3] and [0, 2, 1, 3] are correct.

Show Solution

Approach

Now you need the order itself, and Kahn's algorithm produces it front to back with no reversal step. It's the template with one change: the pairs point the other way. [course, pre] becomes the edge pre -> course, and inDegree[course] counts how many prerequisites course is still waiting on. Courses with none start in the queue. Each time a course is taken, every course that depends on it has one fewer prerequisite left, and any that reach 0 join the queue.

If there's a cycle, its courses never reach 0 and the order comes out short, so return []. In the last demo, course 0 is taken, but courses 1 and 2 each need the other and never become available.

Any valid order is accepted, so the deterministic one here (seeds in ascending order, edges in input order) is just a convenient choice. For the example it returns [0, 1, 2, 3].

Time O(V + E)Space O(V + E)

from collections import deque


def find_order(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    """An order to take every course, given pairs [course, pre] meaning pre must
    be taken before course. Returns [] if a cycle makes that impossible."""
    graph: list[list[int]] = [[] for _ in range(num_courses)]
    in_degree = [0] * num_courses  # Unmet prerequisites per course.
    for course, pre in prerequisites:
        graph[pre].append(course)  # The edge runs pre -> course: pre comes first.
        in_degree[course] += 1
    # Seed with every course that has no prerequisites, in ascending order.
    queue = deque(node for node in range(num_courses) if in_degree[node] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1  # One more prerequisite of neighbor is done.
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    # Courses on a cycle never run out of prerequisites, so they never come out.
    return order if len(order) == num_courses else []


if __name__ == "__main__":
    print(find_order(2, [[1, 0]]))  # [0, 1]
    print(find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))  # [0, 1, 2, 3]
    print(find_order(1, []))  # [0]
    print(find_order(3, [[1, 0], [2, 1], [1, 2]]))  # []

// An order to take every course, given pairs [course, pre] meaning pre must
// be taken before course. Returns [] if a cycle makes that impossible.
export function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const graph: number[][] = Array.from({ length: numCourses }, () => []);
  const inDegree = new Array<number>(numCourses).fill(0); // Unmet prerequisites per course.
  for (const [course, pre] of prerequisites) {
    graph[pre].push(course); // The edge runs pre -> course: pre comes first.
    inDegree[course]++;
  }
  // Seed with every course that has no prerequisites, in ascending order.
  const queue: number[] = [];
  for (let node = 0; node < numCourses; node++) {
    if (inDegree[node] === 0) queue.push(node);
  }
  const order: number[] = [];
  let head = 0; // Dequeue by moving a head index, because shift() is O(n).
  while (head < queue.length) {
    const node = queue[head++];
    order.push(node);
    for (const neighbor of graph[node]) {
      inDegree[neighbor]--; // One more prerequisite of neighbor is done.
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  // Courses on a cycle never run out of prerequisites, so they never come out.
  return order.length === numCourses ? order : [];
}

console.log(JSON.stringify(findOrder(2, [[1, 0]]))); // [0,1]
console.log(JSON.stringify(findOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))); // [0,1,2,3]
console.log(JSON.stringify(findOrder(1, []))); // [0]
console.log(JSON.stringify(findOrder(3, [[1, 0], [2, 1], [1, 2]]))); // []

package main

import "fmt"

// findOrder returns an order to take every course, given pairs [course, pre]
// meaning pre must be taken before course. It returns [] if a cycle makes
// that impossible.
func findOrder(numCourses int, prerequisites [][]int) []int {
	graph := make([][]int, numCourses)
	inDegree := make([]int, numCourses) // Unmet prerequisites per course.
	for _, p := range prerequisites {
		course, pre := p[0], p[1]
		graph[pre] = append(graph[pre], course) // The edge runs pre -> course: pre comes first.
		inDegree[course]++
	}
	// Seed with every course that has no prerequisites, in ascending order.
	queue := []int{}
	for node := 0; node < numCourses; node++ {
		if inDegree[node] == 0 {
			queue = append(queue, node)
		}
	}
	order := []int{}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		order = append(order, node)
		for _, neighbor := range graph[node] {
			inDegree[neighbor]-- // One more prerequisite of neighbor is done.
			if inDegree[neighbor] == 0 {
				queue = append(queue, neighbor)
			}
		}
	}
	// Courses on a cycle never run out of prerequisites, so they never come out.
	if len(order) < numCourses {
		return []int{}
	}
	return order
}

func main() {
	fmt.Println(findOrder(2, [][]int{{1, 0}}))                         // [0 1]
	fmt.Println(findOrder(4, [][]int{{1, 0}, {2, 0}, {3, 1}, {3, 2}})) // [0 1 2 3]
	fmt.Println(findOrder(1, [][]int{}))                               // [0]
	fmt.Println(findOrder(3, [][]int{{1, 0}, {2, 1}, {1, 2}}))         // []
}

using System;
using System.Collections.Generic;

public class Solution
{
    // An order to take every course, given pairs [course, pre] meaning pre must
    // be taken before course. Returns [] if a cycle makes that impossible.
    public static List<int> FindOrder(int numCourses, int[][] prerequisites)
    {
        var graph = new List<List<int>>();
        for (int i = 0; i < numCourses; i++) graph.Add(new List<int>());
        var inDegree = new int[numCourses]; // Unmet prerequisites per course.
        foreach (var p in prerequisites)
        {
            int course = p[0], pre = p[1];
            graph[pre].Add(course); // The edge runs pre -> course: pre comes first.
            inDegree[course]++;
        }
        // Seed with every course that has no prerequisites, in ascending order.
        var queue = new Queue<int>();
        for (int node = 0; node < numCourses; node++)
        {
            if (inDegree[node] == 0) queue.Enqueue(node);
        }
        var order = new List<int>();
        while (queue.Count > 0)
        {
            int node = queue.Dequeue();
            order.Add(node);
            foreach (int neighbor in graph[node])
            {
                inDegree[neighbor]--; // One more prerequisite of neighbor is done.
                if (inDegree[neighbor] == 0) queue.Enqueue(neighbor);
            }
        }
        // Courses on a cycle never run out of prerequisites, so they never come out.
        return order.Count == numCourses ? order : new List<int>();
    }

    public static void Main()
    {
        Console.WriteLine(Format(FindOrder(2, [[1, 0]]))); // [0, 1]
        Console.WriteLine(Format(FindOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))); // [0, 1, 2, 3]
        Console.WriteLine(Format(FindOrder(1, []))); // [0]
        Console.WriteLine(Format(FindOrder(3, [[1, 0], [2, 1], [1, 2]]))); // []
    }

    static string Format(List<int> values) => "[" + string.Join(", ", values) + "]";
}

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

public class Solution {
    // An order to take every course, given pairs [course, pre] meaning pre must
    // be taken before course. Returns [] if a cycle makes that impossible.
    static List<Integer> findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        int[] inDegree = new int[numCourses]; // Unmet prerequisites per course.
        for (int[] p : prerequisites) {
            int course = p[0], pre = p[1];
            graph.get(pre).add(course); // The edge runs pre -> course: pre comes first.
            inDegree[course]++;
        }
        // Seed with every course that has no prerequisites, in ascending order.
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        for (int node = 0; node < numCourses; node++) {
            if (inDegree[node] == 0) queue.add(node);
        }
        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order.add(node);
            for (int neighbor : graph.get(node)) {
                inDegree[neighbor]--; // One more prerequisite of neighbor is done.
                if (inDegree[neighbor] == 0) queue.add(neighbor);
            }
        }
        // Courses on a cycle never run out of prerequisites, so they never come out.
        return order.size() == numCourses ? order : List.of();
    }

    public static void main(String[] args) {
        System.out.println(findOrder(2, new int[][] {{1, 0}})); // [0, 1]
        System.out.println(findOrder(4, new int[][] {{1, 0}, {2, 0}, {3, 1}, {3, 2}})); // [0, 1, 2, 3]
        System.out.println(findOrder(1, new int[][] {})); // [0]
        System.out.println(findOrder(3, new int[][] {{1, 0}, {2, 1}, {1, 2}})); // []
    }
}

Common Pitfalls

Reversing the edges. In the course problems, [a, b] means b comes first, so the edge is b -> a. Get it backwards and Kahn's puts every course before its own prerequisites. A cycle check still gives the right answer, because flipping every edge keeps every cycle, so the mistake can hide until you need the order itself.
Skipping the length check after Kahn's. On a graph with a cycle it quietly returns a partial order instead of failing.
Using a single seen flag for DFS cycle detection on a directed graph. A node reached twice by different paths, like the bottom of a diamond, looks like a cycle when it isn't one.
Starting the DFS only from node 0, or only from nodes with no prerequisites. A cycle can sit where none of those starts reach, so start from every unvisited node.
Expecting one right answer. Most DAGs have many valid orders, so check the order against the edges, or make the choice deterministic (a min-heap gives the smallest order by label).

How It Works

When to Reach for It

Complexity

The Template

Kahn's Algorithm

Worked Problems

Course Schedule

Course Schedule II

Common Pitfalls

Practice