Topological Sort

// Template 1: Kahn's algorithm. Nodes are 0..n-1 and each edge [from, to] means "from must come before to".
// Repeatedly take a node with no remaining incoming edges. Returns a topological order, or [] if there is a cycle.
export function topoSortKahn(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  const indegree = new Array(n).fill(0);
  for (const [from, to] of edges) {
    adj[from].push(to);
    indegree[to]++;
  }
  const queue = [];
  for (let v = 0; v < n; v++) if (indegree[v] === 0) queue.push(v); // nothing has to come before these
  const order = [];
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    order.push(u);
    for (const v of adj[u]) {
      indegree[v]--;                         // the edge u → v is used up
      if (indegree[v] === 0) queue.push(v);  // everything v waited for is now placed
    }
  }
  return order.length === n ? order : [];    // nodes on (or behind) a cycle never reach in-degree 0
}

// Template 2: DFS with three colours. WHITE = not visited, GRAY = on the current path, BLACK = finished.
// An edge into a GRAY node closes a cycle. A node finishes after everything it points to, so the reversed
// finishing order is a topological order. Edges [from, to] mean "from before to". Returns [] on a cycle.
export function topoSortDfs(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [from, to] of edges) adj[from].push(to);
  const WHITE = 0;
  const GRAY = 1;
  const BLACK = 2;
  const color = new Array(n).fill(WHITE);
  const finished = [];

  function visit(u) {                                    // false if a cycle is reachable from u
    color[u] = GRAY;
    for (const v of adj[u]) {
      if (color[v] === GRAY) return false;               // back edge: v is still on the path
      if (color[v] === WHITE && !visit(v)) return false; // BLACK: already finished, nothing to do
    }
    color[u] = BLACK;
    finished.push(u);                                    // everything after u is already in `finished`
    return true;
  }

  for (let u = 0; u < n; u++) {
    if (color[u] === WHITE && !visit(u)) return [];
  }
  return finished.reverse();
}

// Template 3: Kahn's algorithm one round at a time. Each round takes every node whose in-degree is 0 right now,
// e.g. every course you can take this semester. Returns the rounds (arrays of nodes), or null on a cycle.
// The number of rounds is the number of nodes on the longest dependency chain.
export function topoLevels(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  const indegree = new Array(n).fill(0);
  for (const [from, to] of edges) {
    adj[from].push(to);
    indegree[to]++;
  }
  let round = [];
  for (let v = 0; v < n; v++) if (indegree[v] === 0) round.push(v);
  const rounds = [];
  let placed = 0;
  while (round.length > 0) {
    rounds.push(round);
    placed += round.length;
    const next = [];
    for (const u of round) {
      for (const v of adj[u]) {
        indegree[v]--;
        if (indegree[v] === 0) next.push(v); // its last prerequisite was in this round
      }
    }
    round = next;
  }
  return placed === n ? rounds : null;
}