Lesson 24.3 · Topological Sort
Levels, Uniqueness and DP on a DAG
Processing nodes in topological order guarantees all predecessors are done, so you can compute levels, longest paths and earliest finish times in one pass.
12 min
Think of it like this
A cooking schedule: a dish can start only when all its ingredients are prepared, so its earliest finish time is the latest ingredient finish plus its own cooking time.
1.Three things topological order gives you
Levels: process Kahn's queue one level at a time; the number of levels is the minimum number of rounds (semesters) when unlimited tasks run in parallel.
Uniqueness: the order is unique exactly when the queue never holds more than one node.
DP: for each node in order, best[v] = max(best[v], best[u] + w) over edges u → v. That gives longest paths and earliest finish times in O(V + E), which is impossible in general graphs with cycles. A grid where you may only move to larger values is also a DAG, so the same idea (or memoised DFS) solves longest increasing paths.
Remember
- Level count = parallel rounds.
- Queue size 1 throughout = unique order.
- DP in topological order = longest path in a DAG.
Common mistakes
- Trying Dijkstra-style longest paths on graphs with cycles (not well defined).