Topological sort of a DAG

Medium

Problem

Given a directed acyclic graph (n nodes, with edges u → v meaning u must come before v), return any ordering of the nodes in which every edge points forward. In Course Schedule II the edges are prerequisites; return [] if a cycle makes an ordering impossible.

Example 1

Input:  n = 4, edges = [[1,0], [2,0], [3,1], [3,2]]  (course, prerequisite)
Output: [0, 1, 2, 3] or [0, 2, 1, 3]

Also asked as: topological sort · course schedule

Test cases

Case 1

Input:    4, [[0,1],[0,2],[1,3],[2,3]]
Expected (any of): [[0,1,2,3],[0,2,1,3]]

Case 2

Input:    2, [[0,1],[1,0]]
Expected (any of): [null,[]]

Case 3

Input:    1, []
Expected (any of): [[0]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. Kahn's algorithm (BFS on in-degrees)

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

Repeatedly remove a node with in-degree 0 and decrement its neighbours. If you can’t process all nodes, there is a cycle.

function topoSort(numNodes, edges) {
const adj = Array.from({ length: numNodes }, () => []);
const indeg = Array(numNodes).fill(0);
for (const [u, v] of edges) { adj[u].push(v); indeg[v]++; }
const q = [];
for (let i = 0; i < numNodes; i++) if (indeg[i] === 0) q.push(i);
const order = [];
while (q.length) {
const u = q.shift();
order.push(u);
for (const v of adj[u]) if (--indeg[v] === 0) q.push(v);
}
return order.length === numNodes ? order : null; // null ⇒ cycle
}

2. DFS with colours

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

DFS; push a node to the front of the order after its subtree is done. A back-edge to a "grey" node means a cycle.

function topoSort(numNodes, edges) {
const adj = Array.from({ length: numNodes }, () => []);
for (const [u, v] of edges) adj[u].push(v);
const state = Array(numNodes).fill(0); // 0=unseen 1=in-progress 2=done
const order = [];
let ok = true;
const dfs = (u) => {
state[u] = 1;
for (const v of adj[u]) {
if (state[v] === 1) { ok = false; return; }
if (state[v] === 0) dfs(v);
}
state[u] = 2;
order.push(u);
};
for (let i = 0; i < numNodes && ok; i++) if (state[i] === 0) dfs(i);
return ok ? order.reverse() : null;
}