Order tasks so that every task comes after the ones it depends on. Repeatedly take a task with no remaining prerequisites.
Used for
A: 0 left
B: 0, C: 0
D: 0
X needs Y first, and Y needs X first. What happens?
Not quite. Each waits for the other, so nothing can start. Noticing that nothing can start is how topological sort spots a cycle.
Step 1 of 6
Goal: put tasks in an order where each comes after the ones it depends on. A→B, A→C, B→D, C→D means A before B and C, and both before D. Count how many things each task is still waiting for: its in-degree.
Step 2 of 6
A is waiting for nothing (0), so it can go first. Put it in the queue.
Step 3 of 6
Do A and tick it off. B and C were only waiting for A, so both drop to 0 and join the queue.
Step 4 of 6
Do B: D now waits for 1 thing. Do C: D waits for 0 things and joins the queue.
Step 5 of 6
Do D. The order is A, B, C, D. If some tasks never reach 0, they are waiting on each other in a circle and no valid order exists. This is topological sort.
Step 6 of 6
Your turn.
function order(n, edges) { // Kahn's algorithm const adj = Array.from({ length: n }, () => []), indeg = Array(n).fill(0); for (const [a, b] of edges) { adj[a].push(b); indeg[b]++; } const q = [...indeg.keys()].filter(i => !indeg[i]), out = []; while (q.length) { const u = q.shift(); out.push(u); for (const v of adj[u]) if (--indeg[v] === 0) q.push(v); } return out.length === n ? out : []; // [] means a cycle}