Topological patterns

The shape: dependencies want to be a line

A topological order of a directed graph is any ordering of its vertices such that for every edge u → v, u appears before v. It is the answer to every "in what order can I do these tasks given these prerequisites" question — build systems, course schedules, package managers, spreadsheet recalculation, and a surprising number of string and DP problems in disguise.

One theorem carries the whole chapter: a topological order exists if and only if the graph is a DAG (directed, acyclic). A cycle a → b → a demands that a come before b and after it, which no ordering can satisfy. That turns every topological sort into a free cycle detector — and interviewers exploit this constantly, which is why "Course Schedule I" (can it be done at all?) and "Course Schedule II" (give me the order) are the same code with a different return statement.

The order is generally not unique. If two tasks have no dependency path between them, either may go first. Any valid order is accepted; say this out loud, because a candidate who assumes a unique answer often writes a comparison-based sort by mistake.

Kahn's algorithm — BFS over in-degrees

Count how many prerequisites each node has. Everything with zero goes in the queue. Pop one, emit it, and decrement the counter of everything it points at; whenever a counter hits zero, that node's last blocker just cleared, so push it. If you emit fewer than n nodes, the leftovers are all stuck waiting on each other — a cycle.

// edges are [prereq, dependent] pairs. O(V + E) time, O(V + E) space.
function topoSortKahn(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  const indeg = new Array(n).fill(0);
  for (const [u, v] of edges) { adj[u].push(v); indeg[v]++; }

  const queue = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);

  const order = [];
  for (let head = 0; head < queue.length; head++) { // moving index, NOT queue.shift()
    const u = queue[head];
    order.push(u);
    for (const v of adj[u]) {
      if (--indeg[v] === 0) queue.push(v); // last prerequisite cleared — v is now free
    }
  }

  return order.length === n ? order : []; // short order ⇒ a cycle blocked the rest
}

Walking the diagram's graph, with edges 0→1, 0→2, 1→3, 2→3, 3→4:

Dry run: topoSortKahn(5, edges) on the graph from the figure

Step 2 is the one to notice: node 3's counter drops from 2 to 1 and nothing happens. Pushing on "decremented" instead of "reached zero" is the single most common bug in this algorithm, and it produces an order that looks plausible on small examples but violates a prerequisite on any node with two parents.

Two free bonuses fall out of this structure and both come up as follow-ups: the number of nodes popped in a single "round" (drain the entire queue before starting the next) is the count of tasks that can run in parallel, and the number of rounds is the minimum time to finish everything with unlimited workers — which is also the longest path length. Also, if at any point the queue holds more than one node, the topological order is not unique; that is exactly the test for "is there a unique ordering" (Sequence Reconstruction).

DFS topological sort — post-order, then reverse

The DFS version comes at it from the opposite end. Recurse into all of a node's descendants first, and only after they have all been emitted, append the node itself. That builds the order backwards: a node always lands after everything it depends on, so reversing the finished list gives a valid topological order.

Cycle detection is where this version earns its keep — and where it is most often written wrong. A single visited boolean is not enough. You need three states, because seeing an already-visited node means two very different things depending on whether that node is still on the current recursion stack.

const WHITE = 0, GRAY = 1, BLACK = 2; // unvisited / on current path / fully explored

function topoSortDfs(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) adj[u].push(v);

  const state = new Array(n).fill(WHITE);
  const order = [];
  let cyclic = false;

  function dfs(u) {
    state[u] = GRAY; // entering: u is now on the recursion stack

    for (const v of adj[u]) {
      if (state[v] === GRAY) { cyclic = true; return; } // back edge into the current path
      if (state[v] === WHITE) {
        dfs(v);
        if (cyclic) return; // unwind immediately, don't finish this node
      }
      // state[v] === BLACK: cross/forward edge to finished work — safely ignored
    }

    state[u] = BLACK; // leaving: everything reachable from u is already in `order`
    order.push(u);    // POST-order push — this is what makes the reversal correct
  }

  for (let i = 0; i < n; i++) {
    if (state[i] === WHITE) {
      dfs(i);
      if (cyclic) return []; // no valid order exists
    }
  }

  return order.reverse();
}

Default to Kahn in an interview. It is iterative (no stack-depth caveat), the cycle check is a one-line length comparison, and the in-degree array is the hook for every follow-up question. Reach for DFS when you need the actual cycle, or when the same traversal is already computing something else post-order.

Course Schedule I and II — the canonical pair

"Can you finish all numCourses given prerequisites where [a, b] means you must take b before a?" is Course Schedule I. Course Schedule II asks for the ordering itself. One function answers both.

function findOrder(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);

  for (const [course, prereq] of prerequisites) {
    adj[prereq].push(course); // EDGE DIRECTION: prereq -> course, i.e. reversed from the input pair
    indeg[course]++;
  }

  const queue = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) queue.push(i);

  const order = [];
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    order.push(u);
    for (const v of adj[u]) if (--indeg[v] === 0) queue.push(v);
  }

  return order.length === numCourses ? order : [];
}

// Course Schedule I is the same call, thrown away down to a boolean
const canFinish = (n, prereqs) => findOrder(n, prereqs).length === n;

Follow-ups that reuse this exact code: return the lexicographically smallest valid order (replace the queue with a min-heap, cost becomes O(V log V + E)); find the minimum number of semesters if unlimited courses can be taken in parallel (count BFS rounds); detect whether the ordering is unique (a round where the queue held ≥ 2 nodes means it is not).

Alien Dictionary — deriving the graph is the hard part

Given a list of words sorted by an unknown alphabet's order, recover that order. The topological sort at the end is boilerplate; the interview is testing whether you can extract the edges correctly. Two rules do it: compare each adjacent pair of words, and from that pair take only the first position where they differ — everything after it is unconstrained, because lexicographic comparison stopped there.

function alienOrder(words) {
  const adj = new Map(), indeg = new Map();
  for (const w of words) {
    for (const ch of w) {
      if (!adj.has(ch)) { adj.set(ch, new Set()); indeg.set(ch, 0); } // every seen letter must appear in the answer
    }
  }

  for (let i = 0; i + 1 < words.length; i++) {
    const a = words[i], b = words[i + 1];

    // "abc" before "ab" is impossible in ANY alphabet — invalid input, not a cycle
    if (a.length > b.length && a.startsWith(b)) return "";

    for (let j = 0; j < Math.min(a.length, b.length); j++) {
      if (a[j] !== b[j]) {
        if (!adj.get(a[j]).has(b[j])) { // dedupe: a repeated edge would double-count in-degree
          adj.get(a[j]).add(b[j]);
          indeg.set(b[j], indeg.get(b[j]) + 1);
        }
        break; // ONLY the first difference carries information — stop comparing
      }
    }
  }

  const queue = [...indeg.keys()].filter((c) => indeg.get(c) === 0);
  let out = "";
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    out += u;
    for (const v of adj.get(u)) {
      indeg.set(v, indeg.get(v) - 1);
      if (indeg.get(v) === 0) queue.push(v);
    }
  }

  return out.length === indeg.size ? out : ""; // cycle ⇒ the input was contradictory
}

Three failure modes, three different causes, and an interviewer will probe all of them. Prefix violation (["abc", "ab"]) — caught before the loop; it is not a graph problem at all. Cycle (["a","b","a"]) — caught by the length check at the end. Insufficient information (["z","x"] says nothing about y) — not an error; any order among the unconstrained letters is accepted, which is exactly why every letter seen anywhere must be seeded into the maps up front, even letters with no edges at all.

Longest path in a DAG — DP over the topological order

Longest path is NP-hard on a general graph, but on a DAG it is linear. The reason is exactly the property topological order gives you: when you process node u, every edge into u has already been processed, so dist[u] is final and can be relaxed outward without ever being revisited. That is the same argument Dijkstra makes with a priority queue — here the ordering is free and, crucially, negative weights are fine.

// edges: [u, v, weight]. Returns the longest path length in the whole DAG. O(V + E).
function longestPath(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  const indeg = new Array(n).fill(0);
  for (const [u, v, w] of edges) { adj[u].push([v, w]); indeg[v]++; }

  const order = [];
  const queue = [];
  const remaining = indeg.slice(); // copy — we still need the original to seed sources
  for (let i = 0; i < n; i++) if (remaining[i] === 0) queue.push(i);
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    order.push(u);
    for (const [v] of adj[u]) if (--remaining[v] === 0) queue.push(v);
  }
  if (order.length !== n) throw new Error("cycle: longest path is unbounded");

  const dist = new Array(n).fill(-Infinity);
  for (let i = 0; i < n; i++) if (indeg[i] === 0) dist[i] = 0; // any source can start a path

  for (const u of order) {
    if (dist[u] === -Infinity) continue;
    for (const [v, w] of adj[u]) {
      dist[v] = Math.max(dist[v], dist[u] + w); // dist[u] is FINAL — topo order guarantees it
    }
  }

  return Math.max(...dist);
}

Start every distance at Infinity (0 only for the source), skip nodes still at Infinity, flip Math.max to Math.min and read the target's distance instead of the maximum, and you have single-source shortest path on a DAG. It beats Dijkstra's O(E log V) and — unlike Dijkstra — handles negative edge weights correctly. This is worth knowing as a named fact: "if the graph is a DAG, shortest path is O(V + E) by topological order, and negative weights are not a problem."

Once you see this, a whole family of problems reveals itself as topological DP where the graph is implicit and never built:

Minimum Height Trees — peeling leaves is Kahn on a tree

You are given an undirected tree of n nodes and may hang it from any node you like. The height of the tree hung from a root is the distance to the farthest node. Which roots give the smallest height? Trying every root with a BFS each costs O(n²), and with n in the tens of thousands that is too slow, so the structure has to be used.

Derive it from the longest path. Let the tree's longest path (its diameter) have d edges, with end nodes a and b. For any root r, the distances to the two ends add up to at least d (going from a to b by way of r cannot be shorter than the direct path), so one of them is at least d / 2. No root can beat a height of ⌈d / 2⌉, and the middle of that path reaches it. The middle is one node when d is even and two adjacent nodes when d is odd, which is why the answer never has more than two roots.

Finding the middle without finding the path: delete every leaf at once, then delete the leaves of what is left, and repeat. Each round removes both ends of every longest path, shortening it by two edges, so the last one or two nodes standing are exactly the middle. This is Kahn's loop with a different threshold: a leaf is a node of degree 1, and a node becomes a leaf when its degree drops to 1.

function findMinHeightTrees(n, edges) {
  if (n <= 2) return Array.from({ length: n }, (_, i) => i); // 1 node: itself; 2 nodes: both
  const adj = Array.from({ length: n }, () => []);
  const degree = new Array(n).fill(0);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
    degree[a]++;
    degree[b]++;
  }

  let leaves = [];
  for (let i = 0; i < n; i++) if (degree[i] === 1) leaves.push(i);

  let remaining = n;
  while (remaining > 2) { // a tree has one or two centres, so stop at 2 or fewer
    remaining -= leaves.length; // the whole layer goes at once
    const nextLeaves = [];
    for (const leaf of leaves) {
      for (const v of adj[leaf]) {
        if (--degree[v] === 1) nextLeaves.push(v); // v just lost its last child: new leaf
      }
    }
    leaves = nextLeaves;
  }
  return leaves.sort((a, b) => a - b);
}

Dry run: the tree in the figure, edges 0-3, 1-3, 2-3, 3-4, 4-5, 5-6

The round-2 row is the one to watch. Node 4's degree goes 2 → 1 → 0, so it is pushed when it reaches exactly 1 and never again; the later decrement to 0 does nothing because the test is === 1. Time and space are O(n): every node is a leaf at most once and every edge is looked at twice.

Course Schedule IV — answering reachability queries on a DAG

Now the question is not an order but a lookup. You get the prerequisite pairs once, then many queries [u, v] asking "is u a prerequisite of v, directly or through a chain?" The graph is guaranteed to be a DAG. A fresh DFS per query costs O(V + E) each, so q queries cost O(q · (V + E)). When q is large, do the work once and answer every query from a table.

The table is "for each node, the set of all its ancestors." The topological order is what makes it computable in one pass. When node u is popped from Kahn's queue, all of its parents have already been popped, and each parent passed down everything it knew, so ancestors[u] is already complete. Now u hands each child v its own ancestors plus u itself. A child that has several parents collects the union from all of them.

function checkIfPrerequisite(n, prerequisites, queries) {
  const adj = Array.from({ length: n }, () => []);
  const indeg = new Array(n).fill(0);
  for (const [a, b] of prerequisites) {
    adj[a].push(b); // a must come before b
    indeg[b]++;
  }

  const ancestors = Array.from({ length: n }, () => new Set()); // everything that reaches v
  const queue = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);

  for (let head = 0; head < queue.length; head++) {
    const u = queue[head]; // ancestors[u] is complete: every parent of u was popped earlier
    for (const v of adj[u]) {
      ancestors[v].add(u);
      for (const a of ancestors[u]) ancestors[v].add(a);
      if (--indeg[v] === 0) queue.push(v);
    }
  }

  return queries.map(([u, v]) => ancestors[v].has(u));
}

Dry run: edges 0→1, 0→2, 1→3, 2→3, 3→4

The query [0, 4] is ancestors[4].has(0), true; the query [4, 0] asks whether 4 is in ancestors[0], which is empty, so false. Time is O(V + E · V) in the worst case, because each edge may copy a set of up to V elements, and space is O(V²) for the sets. Queries then cost O(1) each.

The shorter alternative is Floyd–Warshall on a boolean matrix, O(V³) time and O(V²) space, which ignores the topological order entirely and also works when the graph is not a DAG. For a few hundred nodes it is perfectly good, and it is short:

function checkIfPrerequisiteFloyd(n, prerequisites, queries) {
  const reach = Array.from({ length: n }, () => new Array(n).fill(false));
  for (const [a, b] of prerequisites) reach[a][b] = true;

  for (let k = 0; k < n; k++) { // k, the allowed middle node, MUST be the outer loop
    for (let i = 0; i < n; i++) {
      if (!reach[i][k]) continue;
      for (let j = 0; j < n; j++) {
        if (reach[k][j]) reach[i][j] = true;
      }
    }
  }
  return queries.map(([u, v]) => reach[u][v]);
}

Parallel Courses — rounds first, then durations

The first version asks for the fewest semesters when you may take any number of courses per semester, provided their prerequisites were finished in earlier semesters. Kahn's algorithm run one layer at a time answers it directly: the courses ready now all fit in this semester, and the courses they free have to wait for the next one.

function minimumSemesters(n, relations) {
  const adj = Array.from({ length: n + 1 }, () => []);
  const indeg = new Array(n + 1).fill(0);
  for (const [prev, next] of relations) {
    adj[prev].push(next);
    indeg[next]++;
  }

  let ready = [];
  for (let c = 1; c <= n; c++) if (indeg[c] === 0) ready.push(c);

  let semesters = 0, taken = 0;
  while (ready.length > 0) {
    semesters++; // everything in "ready" fits in this one semester
    const nextReady = [];
    for (const u of ready) {
      taken++;
      for (const v of adj[u]) if (--indeg[v] === 0) nextReady.push(v);
    }
    ready = nextReady; // courses freed now can only start next semester
  }
  return taken === n ? semesters : -1; // fewer taken than n: a cycle blocked the rest
}

The number of layers equals the number of courses on the longest prerequisite chain, because a chain of k courses forces k semesters and nothing forces more. For n = 3 and relations [[1, 3], [2, 3]] the first layer is [1, 2], the second is [3], and the answer is 2. For the cycle [[1, 2], [2, 3], [3, 1]] nothing has in-degree 0, nothing is taken, and the check taken === n fails, so the answer is -1. The loop must snapshot ready and build nextReady separately; if you push freed courses into the layer you are still iterating, you merge semesters and under-count.

The harder cousin gives every course a duration, and now "layers" no longer measure time: a layer holding a one-month course and a ten-month course lasts ten months. The right quantity is each course's earliest finish time, and it is exactly the longest-path DP from earlier in this chapter with the weight on the node instead of the edge: finish[v] = time[v] + max(finish[u] over prerequisites u). Courses with no prerequisites start at month 0. The answer is the largest finish time.

function minimumTime(n, relations, time) { // time[c - 1] = months course c takes
  const adj = Array.from({ length: n + 1 }, () => []);
  const indeg = new Array(n + 1).fill(0);
  for (const [prev, next] of relations) {
    adj[prev].push(next);
    indeg[next]++;
  }

  const finish = new Array(n + 1).fill(0); // earliest month course c can be done
  const queue = [];
  for (let c = 1; c <= n; c++) {
    if (indeg[c] === 0) {
      queue.push(c);
      finish[c] = time[c - 1]; // a source starts at month 0 and takes its own time
    }
  }

  let taken = 0, total = 0;
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    taken++;
    total = Math.max(total, finish[u]);
    for (const v of adj[u]) {
      finish[v] = Math.max(finish[v], finish[u] + time[v - 1]); // wait for the slowest prerequisite
      if (--indeg[v] === 0) queue.push(v);
    }
  }
  return taken === n ? total : -1;
}

Dry run: 5 courses, times [1, 2, 3, 4, 5], relations 1→5, 2→5, 3→5, 3→4, 4→5

The same skeleton scales up. If you must carry more than a number through the DAG, such as "the highest count of any single colour along a path" (Largest Color Value in a Directed Graph), give every node an array of counts, merge parents with an element-wise max, and keep the same cycle check at the end.

Sequence Reconstruction — is the order unique?

You have a permutation nums of 1..n and a list of sequences, each a subsequence of the secret order. Is nums the only order consistent with all the sequences? Every consecutive pair in a sequence is an ordering fact, so build the edges and ask for a topological order. Uniqueness is the part to derive: two nodes can be swapped exactly when they are free at the same moment, so the order is unique if and only if the queue holds exactly one node at every step. The queue already shows it, with no extra work.

function sequenceReconstruction(nums, sequences) {
  const n = nums.length;
  const adj = Array.from({ length: n + 1 }, () => new Set());
  const indeg = new Array(n + 1).fill(0);
  const seen = new Set();

  for (const seq of sequences) {
    for (let i = 0; i < seq.length; i++) {
      if (seq[i] < 1 || seq[i] > n) return false;
      seen.add(seq[i]);
      if (i > 0 && !adj[seq[i - 1]].has(seq[i])) { // each edge counted once
        adj[seq[i - 1]].add(seq[i]);
        indeg[seq[i]]++;
      }
    }
  }
  if (seen.size !== n) return false; // a number no sequence mentions can go anywhere

  let queue = [];
  for (let v = 1; v <= n; v++) if (indeg[v] === 0) queue.push(v);

  let placed = 0;
  while (queue.length > 0) {
    if (queue.length > 1) return false; // two free nodes can swap: the order is not unique
    const u = queue.pop();
    if (nums[placed++] !== u) return false; // the one possible order is not nums
    for (const v of adj[u]) if (--indeg[v] === 0) queue.push(v);
  }
  return placed === n; // short of n: a cycle
}

Dry run: nums = [1, 2, 3]

There is an equivalent view that is worth knowing: the order is unique exactly when every neighbouring pair nums[i], nums[i + 1] appears next to each other in some sequence, so each step is forced by a direct edge. The queue version checks the same thing and also catches contradictions as a bonus.

Longest Increasing Path in a Matrix — a DAG you never build

From a cell you may step up, down, left or right, but only onto a strictly larger value. How many cells can the longest such walk visit? The cells are nodes and each allowed step is an edge. Because every step strictly increases the value, you can never return to a cell, so this graph has no cycles and needs no visited set. That is the topological DP from earlier, with the order left implicit: longestFrom(cell) is 1 plus the best of longestFrom over the larger neighbours, memoized.

const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];

function longestIncreasingPath(matrix) {
  const rows = matrix.length;
  if (rows === 0) return 0;
  const cols = matrix[0].length;
  const memo = Array.from({ length: rows }, () => new Array(cols).fill(0)); // 0 = not computed yet

  function longestFrom(r, c) { // cells on the longest increasing path that starts at (r, c)
    if (memo[r][c] !== 0) return memo[r][c];
    let best = 1;
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (matrix[nr][nc] > matrix[r][c]) best = Math.max(best, 1 + longestFrom(nr, nc)); // strictly larger only
    }
    memo[r][c] = best;
    return best;
  }

  let answer = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) answer = Math.max(answer, longestFrom(r, c));
  }
  return answer;
}

Each cell is computed once and looks at four neighbours, so the time is O(m · n) for an m × n grid, with O(m · n) memory for the table. Memoization is the whole speedup: the same code with a visited array that is set and cleared (backtracking style) walks every increasing path one by one, and the number of paths can be exponential: on a 12 × 12 grid whose values grow along both rows and columns, stepping only right or down already gives 2,704,155 walks from the corner alone.

The iterative version is Kahn's algorithm again. A cell's in-degree is the number of strictly smaller neighbours, because those are the cells that can step onto it. Cells with in-degree 0 are local minima, the places a longest path can start. Peel them layer by layer; the number of layers is the answer, because each layer extends every chain by one cell.

function longestIncreasingPathKahn(matrix) {
  const rows = matrix.length;
  if (rows === 0) return 0;
  const cols = matrix[0].length;
  const inDegree = Array.from({ length: rows }, () => new Array(cols).fill(0));
  let layer = [];

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      for (const [dr, dc] of DIRS) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] < matrix[r][c]) inDegree[r][c]++;
      }
      if (inDegree[r][c] === 0) layer.push([r, c]); // no smaller neighbour: a path can start here
    }
  }

  let layers = 0;
  while (layer.length > 0) {
    layers++;
    const next = [];
    for (const [r, c] of layer) {
      for (const [dr, dc] of DIRS) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
        if (matrix[nr][nc] > matrix[r][c] && --inDegree[nr][nc] === 0) next.push([nr, nc]);
      }
    }
    layer = next;
  }
  return layers; // the number of layers is the length of the longest chain
}

Dry run: [[9, 9, 4], [6, 6, 8], [2, 1, 1]]

Four layers, so the answer is 4, for example 1 → 2 → 6 → 9. The recursive version is simpler to write, but its depth equals the length of the longest increasing path, and an interview grid can force a path through most of its cells. In a quick test on Node 24, a single row of 5,000 increasing numbers throws RangeError: Maximum call stack size exceeded for the memoized DFS above, while the layer version handles it without recursion. Mention the trade-off.

Eventual Safe States — peel from the sinks

In a directed graph, a terminal node has no outgoing edges. A node is safe if every path that starts at it ends at a terminal node after a finite number of steps. Put differently: a node is unsafe exactly when it can reach a cycle, since then a path can circle forever. Return all safe nodes in ascending order.

Think of Kahn's algorithm with the edges turned around. Terminal nodes are safe by definition. A node all of whose outgoing edges lead to safe nodes is safe too, because every path from it passes through one of them. So peel from the sinks inward: track each node's out-degree (how many of its successors are not yet known to be safe), start the queue with out-degree 0, and when a node is declared safe, decrement the out-degree of everything that points at it. The decrement needs the reversed graph, which is why this build flips every edge. Nodes that never reach 0 are on a cycle or lead into one.

function eventualSafeNodes(graph) {
  const n = graph.length;
  const reverse = Array.from({ length: n }, () => []);
  const outDegree = new Array(n).fill(0);
  for (let u = 0; u < n; u++) {
    outDegree[u] = graph[u].length;
    for (const v of graph[u]) reverse[v].push(u); // flip every edge: v now points back at u
  }

  const queue = [];
  for (let u = 0; u < n; u++) if (outDegree[u] === 0) queue.push(u); // terminal nodes are safe

  const safe = new Array(n).fill(false);
  for (let head = 0; head < queue.length; head++) {
    const v = queue[head];
    safe[v] = true;
    for (const u of reverse[v]) {
      if (--outDegree[u] === 0) queue.push(u); // every edge out of u now leads to a safe node
    }
  }

  const result = [];
  for (let u = 0; u < n; u++) if (safe[u]) result.push(u); // scan by label: the answer must be sorted
  return result;
}

Dry run: graph = [[1,2],[2,3],[5],[0],[5],[],[]]

Safe nodes are 2, 4, 5, 6. Nodes 0, 1 and 3 form the cycle 0 → 1 → 3 → 0, so they stay stuck at out-degree 1 and are never emitted. Time and space are O(V + E).

The DFS version asks the same question from the node's side with the three states you saw earlier. A node is safe when the DFS from it never touches a GRAY node:

function eventualSafeNodesDfs(graph) {
  const n = graph.length;
  const state = new Array(n).fill(0); // 0 unvisited, 1 on the current path, 2 known safe

  function isSafe(u) {
    if (state[u] === 1) return false; // back into the current path: a cycle
    if (state[u] === 2) return true;
    state[u] = 1;
    for (const v of graph[u]) {
      if (!isSafe(v)) return false; // u stays 1 on purpose: it leads into a cycle
    }
    state[u] = 2;
    return true;
  }

  const result = [];
  for (let u = 0; u < n; u++) if (isSafe(u)) result.push(u);
  return result;
}

One loop, three thresholds

Look back at what you wrote in this chapter. Course Schedule, Parallel Courses, Course Schedule IV, Sequence Reconstruction and the grid problem all peel nodes whose in-degree has fallen to 0. Minimum Height Trees peels nodes whose degree has fallen to 1. Eventual Safe States peels nodes whose out-degree has fallen to 0, on the reversed graph. The loop is identical each time: remove what is finished, decrement its neighbours, queue whatever just reached the threshold.

When a new problem mentions "remove … repeatedly until nothing is left" or asks for the nodes that survive or fall away, name the counter and the threshold before writing code. That choice is the whole design.

Recognizing it in an unseen problem

• The words "prerequisite," "depends on," "must come before," "build order," "compile," "recipe/ingredient," or any input of ordered pairs [a, b] meaning "a then b."
• The question is "is this even possible?" — that is cycle detection, and a topological sort answers it as a side effect (emitted count < n).
• Sorted or ranked input that implies relative order between symbols (Alien Dictionary, Sequence Reconstruction, Verifying an Alien Dictionary's harder cousins) — the edges must be derived, and only adjacent pairs at the first differing position carry information.
• "Minimum number of rounds/semesters/steps with unlimited parallelism" → Kahn, counting BFS levels. "Is the order unique?" → check whether the queue ever holds two nodes at once.
• Longest/shortest/count-of paths where the graph provably has no cycles → do not reach for Dijkstra or Bellman-Ford; relax edges in topological order for O(V + E), negative weights included.
• A tree problem asks for its "centre", or for what is left after repeatedly removing leaves → peel layers of degree-1 nodes (Minimum Height Trees), do not try every root.
• Many reachability or "is X before Y" queries on a DAG → compute each node's ancestor set once in topological order, then answer queries by lookup.
• A grid or array where every move must go strictly up (or down) in value → the cells already form a DAG; memoize or peel layers, and skip the visited set.
• "Which nodes are safe / cannot reach a cycle" → peel from the sinks on the reversed graph, with out-degree as the counter.
• Distinguish from plain BFS/DFS: ordinary traversal visits a node the first time it is reached; topological sort must wait until every incoming edge is satisfied. If a node has two parents and you emit it after seeing only one, you have written BFS, not a topological sort.
• Distinguish from Union-Find: undirected connectivity and cycle detection in an undirected graph is Union-Find's job; direction and ordering is this chapter's.