Engineering practice · 30 MIN

Order jobs and detect dependency cycles

A topological order exists only for a directed acyclic graph.

Kahn’s algorithm starts with jobs whose indegree is zero. Remove one job, decrement its dependants, and enqueue each newly ready job. A cycle leaves some jobs unprocessed. Our deterministic contract seeds the queue in job-index order and visits outgoing edges in input order. A cursor over an array avoids repeatedly shifting its contents.

Treat the function as a small service: define a contract, maintain an invariant, and test the boundaries.

Read the example

const ready = [0, 2];
let head = 0;
while (head < ready.length) console.log(ready[head++]);

0
2

Your challenge

Input {count, edges}: jobs are 0..count-1 and each unique edge [before,after] requires before first. Return the Kahn queue order, or [] if a cycle exists. Seed zero-indegree jobs in ascending order and process outgoing edges in input order.

Solution cost: O(V + E) time · O(V + E) space

Common trap

Array(count).fill([]) shares one array among every node. Use Array.from with a factory.

Further reading: Princeton: directed graphs