A DAG (directed acyclic graph) is a dependency graph that does not argue with itself. Course 1 before course 2 before course 3 is a DAG. 'A requires B and B requires A' is a cycle, and then there is no order that respects every prerequisite.
A topological order is an array ord of all n nodes such that for every edge u → v, u appears before v. Not unique in general. If ord.length < n after the algorithm, you found a cycle — return 'impossible', do not invent the missing nodes.
function topoKahn(n, adj) {
const indeg = Array(n).fill(0);
for (let u = 0; u < n; u++) for (const v of adj[u]) indeg[v]++;
const q = [];
for (let u = 0; u < n; u++) if (indeg[u] === 0) q.push(u);
const ord = [];
for (let h = 0; h < q.length; h++) {
const u = q[h];
ord.push(u);
for (const v of adj[u]) {
indeg[v]--;
if (indeg[v] === 0) q.push(v);
}
}
return ord.length === n ? ord : null; // null ⇒ cycle
}DFS finish times. Run a 3-color DFS. When a node paints black (all descendants done), prepend it to the order (or append and reverse at the end). Edges to gray still mean a cycle — abort. The reverse finish order is a topo if and only if there was no back edge.
Kahn and DFS answer the same question. Kahn is often easier to prove 'cycle ⇔ leftover nodes'. DFS is the same walk you already write for cycle detection, so Course Schedule (canFinish) can be either.
function topoDfs(n, adj) {
const color = Array(n).fill(0);
const ord = [];
function dfs(u) {
color[u] = 1;
for (const v of adj[u]) {
if (color[v] === 1) return false;
if (color[v] === 0 && !dfs(v)) return false;
}
color[u] = 2;
ord.push(u); // reverse later
return true;
}
for (let u = 0; u < n; u++) {
if (color[u] === 0 && !dfs(u)) return null;
}
ord.reverse();
return ord;
}Checks 0/2