• Overview: DAGs and Topological Ordering
• Kahn's Algorithm (BFS on in-degrees)
• DFS Finishing Order
• DAG DP Patterns (paths, longest path, ways)
• Applications
• Pitfalls and Checks
• Exercises

• DAG: directed graph with no cycles.
• Topological order: for every edge u→v, u appears before v.
• Existence: only DAGs admit a topological order; use it to linearize dependencies.

// Returns topological order or empty array if cycle exists
function topoSortKahn(adj) {
  const n = adj.length;
  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 order = [];
  for (let qi = 0; qi < q.length; qi++) {
    const u = q[qi]; order.push(u);
    for (const v of adj[u]) if (--indeg[v] === 0) q.push(v);
  }
  return order.length === n ? order : [];
}

• Cycle check: if order size < n, a cycle exists.
• Complexity: O(n + m).

// Topo order by DFS postorder
function topoSortDFS(adj) {
  const n = adj.length, vis = Array(n).fill(0); // 0=unseen,1=stack,2=done
  const order = []; let hasCycle = false;
  function go(u) {
    vis[u] = 1;
    for (const v of adj[u]) {
      if (vis[v] === 0) go(v);
      else if (vis[v] === 1) { hasCycle = true; }
    }
    vis[u] = 2; order.push(u);
  }
  for (let u = 0; u < n; u++) if (vis[u] === 0) go(u);
  if (hasCycle) return [];
  order.reverse();
  return order;
}

• Detection: a back-edge during DFS implies a cycle → no topo order.

// Count number of paths from source s to every node
function countPathsDAG(adj, s) {
  const order = topoSortKahn(adj);
  if (order.length === 0) throw new Error('Graph has a cycle');
  const ways = Array(adj.length).fill(0);
  ways[s] = 1;
  for (const u of order) for (const v of adj[u]) ways[v] += ways[u];
  return ways;
}

// Longest path in DAG with weights on edges (assume weight[u][v])
function longestPathDAG(adj, weight, s) {
  const n = adj.length; const order = topoSortKahn(adj);
  if (order.length === 0) throw new Error('Graph has a cycle');
  const dist = Array(n).fill(-Infinity); dist[s] = 0;
  for (const u of order) if (dist[u] > -Infinity) {
    for (const v of adj[u]) dist[v] = Math.max(dist[v], dist[u] + weight[u][v]);
  }
  return dist;
}

• General rule: DP state per node; transition along edges following topo order.
• Init: set base nodes before iterating (e.g., ways[s] = 1, dist[s] = 0).

• Build systems and dependency resolution.
• Course scheduling and prerequisite planning.
• DP on partial orders (e.g., longest chain problems).

• Graph must be acyclic; always check cycle condition.
• Multiple sources: all in-degree 0 nodes can start.
• Disconnected DAGs: topo order still exists; process all components.

1. Implement Kahn's algorithm and verify cycle detection.
2. Compute number of paths from sources to sinks in a DAG.
3. Given weighted DAG, find the longest path from s to all nodes.