Topological sort (Kahn's algorithm)

O(V+E)

Repeatedly take a node with zero unmet prerequisites, place it, and remove its outgoing edges, which can free up nodes that were only waiting on it. If nodes remain but none are free, the dependencies form a cycle and no valid order exists.

Signals

task must come before anotherorder that respects dependenciesdetect a cycle in prerequisitesbuild order / course schedule / install orderdirected graph, X must happen before Y

Template

function topoSort(n, adj) {
    const indeg = new Array(n).fill(0);
    for (const u in adj) for (const v of adj[u]) indeg[v]++;
    const queue = [];
    for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);
    const order = [];
    while (queue.length) {
        const u = queue.shift();
        order.push(u);
        for (const v of adj[u] || []) {
            if (--indeg[v] === 0) queue.push(v);
        }
    }
    return order.length === n ? order : null; // null: a cycle exists
}

Looks similar, isn't

Graph BFS / DFS: Topological sort orders a DAG by dependency, and a cycle means no valid order exists at all. A plain traversal just visits every reachable node and gives no ordering guarantee and no cycle verdict.

V, E up to ~1e5, directed dependency graph, need one valid order or a cycle report -> O(V+E): Kahn's in-degree queue visits every node and edge once.

Learn this pattern