Topological Sort & DAG DP
Why this exists
Most real constraints are of the form "this before that". You cannot link a binary before its object files are compiled, take Algorithms II before Algorithms I, pour the roof before the walls, or evaluate a spreadsheet cell before the cells it references. Write each constraint as a directed edge u → v meaning "u must come before v", and the question "in what order can I do everything?" becomes: list the vertices so that every edge points forward. That list is a topological order, and the procedure that finds it is topological sorting.
An order exists exactly when the graph has no directed cycle. A directed graph with no cycle is a DAG (directed acyclic graph), and DAGs are the natural shape of dependencies: build targets, package requirements, course prerequisites, task networks, data pipelines, the states of most dynamic programs. If the graph does have a cycle, no order works (A before B before C before A), and the same algorithm that sorts a DAG will tell you so. That makes topological sort a cycle detector too, which is often the real question ("can every course be finished?").
The algorithms are old and simple. Arthur B. Kahn published the "repeatedly remove a vertex with no incoming edges" method in 1962 ("Topological sorting of large networks", Communications of the ACM 5(11)), motivated by PERT networks for large engineering projects. The depth-first version, "output vertices in reverse order of finishing", is due to Robert Tarjan (1976) and appears in CLRS section 22.4. Both run in — linear, the best possible, since any correct algorithm has to look at every edge.
The second half of this lesson is about what you do with a topological order. Once vertices are sorted so every edge points forward, you can compute anything of the form "best/total over all paths into v" in one left-to-right sweep: longest path, shortest path with negative edges, number of paths, earliest start times, slack in a schedule. That sweep is DAG dynamic programming, and it is the bridge to Module 6, where "DP on Graphs & DAGs" shows that every dynamic program is a path problem on a DAG of states. The Graphs overview introduces both topological sort algorithms in a few lines; this lesson proves them, extends them, and shows where they run.
Pattern triggers
| If the problem says or has… | …think of |
|---|---|
| "prerequisites", "depends on", "must happen before", "requires" | Edges prereq → course; topological sort |
| "Is it possible to finish all…?", "Is the schedule valid?" | Cycle detection: Kahn's output count, or DFS gray-node check |
| "Return any valid order" | Kahn (BFS) or DFS reverse postorder |
| "Return the lexicographically smallest order" | Kahn with a min-heap instead of a queue |
| "Minimum number of semesters / rounds / days, unlimited per round" | Kahn level by level = longest path counted in vertices |
| "Each task has a duration; minimum total time with unlimited workers" | Critical path: longest weighted path in the DAG |
| "Longest path", "longest chain", "longest increasing path" on a DAG or a grid with a strict order | DAG DP in topological order |
| "Number of ways / paths from s to t" with no cycles | DAG DP: ways[v] = Σ ways[u] over edges u → v |
| "Given a sorted list of words in an unknown alphabet" | Build letter edges from adjacent words, then topological sort |
| "Is u a prerequisite of v?" for many queries | Transitive closure in topological order (bitsets) |
| "Order is unique?" / "Can the sequence be reconstructed?" | Kahn with the queue never holding more than one vertex |
| "Nodes from which every path ends in a terminal" | Kahn on the reversed graph (peel sinks) |
| Grid where you may only move to strictly larger values | Implicit DAG; sort cells by value or memoized DFS |
The negative signals matter as much. If the graph is undirected, "topological order" makes no sense. If cycles are allowed and you need ordering inside cycles, first collapse strongly connected components (Connectivity), then sort the resulting DAG.
Intuition & first principles
Think of a pile of tasks on a table, each with sticky notes saying which other tasks must be done first. What can you do right now? Exactly the tasks with no sticky notes left. Do one; then tear its name off every other task's notes. New tasks become note-free. Keep going. If at some point tasks remain but every one of them still has a note, you are stuck, and the only way to be stuck is a circular chain of "first do X".
That is Kahn's algorithm, and every word maps to a data structure:
- "tasks with no notes left" — vertices with in-degree 0, where the in-degree of is the number of edges entering from vertices not yet output. Such a vertex is a source of the remaining graph.
- "tear its name off other notes" — for each edge , decrement the in-degree of .
- "the pile of ready tasks" — a queue (any container works; the choice only changes which valid order you get).
Two facts make it work. First, every non-empty DAG has a source. Start anywhere and walk backwards along incoming edges. If no vertex were a source you could walk forever, but there are only vertices, so you would revisit one, and the backward walk between the two visits is a cycle. Second, removing a source from a DAG leaves a DAG, because deleting vertices cannot create cycles. So "take a source, delete it, repeat" never gets stuck on a DAG and outputs every vertex. Each output vertex has had all its predecessors output before it, which is exactly the definition of a topological order.
The DFS view is different and just as natural. Run depth-first search. When DFS finishes a vertex (all its out-neighbours explored), everything reachable from has already finished. So if you write vertices down at finishing time, every vertex appears after everything that depends on it. Reverse that list and every edge points forward. Formally: a topological order is the reverse postorder of a DFS.
Precisely, for a directed graph , a topological order is a bijection such that for every edge . It exists if and only if is acyclic. It is usually not unique: the 7-vertex DAG used below has 21 of them.
Mechanics
The running example is this DAG. Read A → B as "A must come before B".
flowchart LR
A["A (in 0)"] --> B["B (in 1)"]
A --> C["C (in 2)"]
F["F (in 0)"] --> C
F --> G["G (in 1)"]
B --> D["D (in 2)"]
C --> D
D --> E["E (in 2)"]
G --> E
Kahn's algorithm
indeg[v] = number of edges into v, for every v
q = queue containing every v with indeg[v] == 0
order = []
while q is not empty:
u = q.pop_front(); order.append(u)
for each edge u -> v:
indeg[v] -= 1
if indeg[v] == 0: q.push_back(v)
if len(order) < |V|: the graph has a cycle (the unprocessed vertices lie on or behind one)
return order
flowchart TD
S["Compute in-degrees"] --> Q["Enqueue all in-degree-0 vertices"]
Q --> L{"Queue empty?"}
L -->|"no"| P["Pop u, append to order"]
P --> R["For each u -> v: indeg[v] -= 1"]
R --> Z{"indeg[v] == 0?"}
Z -->|"yes"| PU["Push v"]
Z -->|"no"| L
PU --> L
L -->|"yes"| C{"len(order) == V?"}
C -->|"yes"| OK["Return order: graph is a DAG"]
C -->|"no"| CY["Cycle detected"]
Trace: Kahn on the example
Initial in-degrees: A 0, B 1, C 2, D 2, E 2, F 0, G 1. Vertices with in-degree 0 are enqueued in alphabetical order. Values below come from running the trace generator (scripts/traces/kahn_topo.py).
| Step | Pop | Edges removed → new in-degree | Queue after | Order so far |
|---|---|---|---|---|
| 0 | — | (initial) | A, F | — |
| 1 | A | B → 0, C → 1 | F, B | A |
| 2 | F | C → 0, G → 0 | B, C, G | A F |
| 3 | B | D → 1 | C, G | A F B |
| 4 | C | D → 0 | G, D | A F B C |
| 5 | G | E → 1 | D | A F B C G |
| 6 | D | E → 0 | E | A F B C G D |
| 7 | E | (none) | empty | A F B C G D E |
Seven vertices out of seven were output, so the graph is acyclic. Every edge points forward in A F B C G D E: check F → C (positions 2, 4) and G → E (5, 7).
Now add one edge E → C, which closes the cycle C → D → E → C. In-degrees become C 3, D 2, E 2. Kahn outputs A F B G and stops: C still has in-degree 1 (from E), D has 1 (from C), E has 1 (from D). Each stuck vertex is waiting for another stuck vertex. The count, 4 < 7, is the cycle signal. Note that the stuck set is "vertices on a cycle or reachable from one": a vertex downstream of a cycle can never reach in-degree 0 either. To list an actual cycle, start at any stuck vertex and walk backwards along edges from other stuck vertices until a vertex repeats.
DFS finishing order
color[v] = WHITE for all v
for each v in V: if color[v] == WHITE: visit(v)
visit(u):
color[u] = GRAY # on the current DFS path
for each edge u -> v:
if color[v] == GRAY: cycle! # back edge
if color[v] == WHITE: visit(v)
color[u] = BLACK # finished
post.append(u)
return reverse(post)
The three colours are not decoration. White means unvisited, gray means "on the recursion stack right now", black means "finished, everything reachable from it is done". An edge into a gray vertex points back up the current path, which is a cycle. An edge into a black vertex is harmless (a cross or forward edge). Using only a boolean visited cannot tell gray from black, which is the single most common bug in cycle detection for directed graphs (it is correct for undirected graphs, which is why people carry it over).
flowchart LR
W["WHITE: not yet seen"] -->|"visit(u) starts"| G["GRAY: on the stack"]
G -->|"all out-edges done"| B["BLACK: finished, appended to post"]
G -.->|"edge to a GRAY vertex"| CY["back edge = cycle"]
Trace: DFS on the example
Roots are tried in alphabetical order, out-edges in the order listed (A → B before A → C). d is discovery time, f finishing time. Values from a throwaway script.
| Time | Event | Stack (gray) | Note | post |
|---|---|---|---|---|
| 1 | discover A | A | ||
| 2 | discover B | A B | ||
| 3 | discover D | A B D | ||
| 4 | discover E | A B D E | E has no out-edges | |
| 5 | finish E | A B D | E | |
| 6 | finish D | A B | E D | |
| 7 | finish B | A | E D B | |
| 8 | discover C | A C | C → D: D is black, skip | E D B |
| 9 | finish C | A | E D B C | |
| 10 | finish A | E D B C A | ||
| 11 | discover F | F | F → C: black, skip | E D B C A |
| 12 | discover G | F G | G → E: black, skip | E D B C A |
| 13 | finish G | F | E D B C A G | |
| 14 | finish F | E D B C A G F |
Reverse postorder: F G A C B D E. It differs from Kahn's A F B C G D E; both are valid. Every edge goes from a later finish to an earlier finish: A → C has , F → C has .
Which order do you get?
Both algorithms produce a topological order. Which one depends on tie-breaking: the queue discipline in Kahn, the root and adjacency order in DFS. If the problem says "any valid order", either is fine. If it says "lexicographically smallest", use a min-heap in Kahn (next section). If a judge compares against one specific order, read the statement for the tie-break rule before blaming your algorithm.
Lexicographically smallest order
Replace Kahn's queue with a min-heap. On the example, the heap version outputs A B F C D G E: after A it can take B (smaller than F), whereas the FIFO queue took F because F was enqueued earlier.
Why greedy is right: at every moment, the set of vertices that may legally come next is exactly the set of sources of the remaining graph, and each one of them really can come next (remove it, the rest is still a DAG and can be finished). So the lexicographically smallest order must start with the smallest current source, and by induction on the remaining graph the whole greedy sequence is lexicographically smallest. Cost: .
A trap: "lexicographically smallest" is not the same as "put vertex 1 as early as possible, then vertex 2 as early as possible, …". Take three vertices with one edge 3 → 1. The lexicographically smallest order is 2 3 1, which puts vertex 1 third. The order 3 1 2 puts vertex 1 second. For the "smallest labels as early as possible" objective, run Kahn on the reversed graph with a max-heap and reverse the output: reversed edge 1 → 3, the max-heap takes 2, then 1, then 3, giving 2 1 3, reversed 3 1 2. The reason is that greedily placing the largest label last is safe (an exchange argument from the back), whereas greedily placing the smallest label first is not. CSES "Course Schedule II" tests exactly this.
Counting topological orders
How many valid orders exist? For general DAGs this is #P-complete (Brightwell and Winkler, "Counting linear extensions", Order 8, 1991), so expect exponential algorithms. For or so, a subset DP works: let ways[S] be the number of ways to order the vertex set as a valid prefix. A vertex can be appended iff all its predecessors are in :
Start with ways[∅] = 1; the answer is ways[V]. With predecessor sets stored as bitmasks, this is time and memory. For the example it gives 21, which the code below double-checks by brute force over all permutations. For a forest (each vertex has at most one parent) there is a closed form, where size is the subtree size, the "hook length formula for trees".
Level-by-level Kahn: minimum number of rounds
If any number of tasks can run in the same round as long as their prerequisites finished in earlier rounds, the minimum number of rounds is the number of vertices on the longest path. Kahn computes it by processing the queue one level at a time: round 1 takes all initial sources, round 2 takes everything freed by round 1, and so on. On the example: round 1 {A, F}, round 2 {B, C, G}, round 3 {D}, round 4 {E}, so 4 rounds, matching the longest chain A → B → D → E (or A → C → D → E).
The equivalent DP is level[v] = 1 + max(level[u]) over edges u → v (sources get 1). This is "Parallel Courses" in its unlimited form. If each round can take at most tasks, the problem changes character completely: minimizing the number of rounds for unit tasks on machines is NP-hard when is part of the input (Ullman, 1975), polynomial for (Coffman and Graham, 1972), and contest versions ("Parallel Courses II") have and expect bitmask DP. Greedy "take the vertices with the most descendants" is a common wrong answer there.
DAG DP: longest path, number of paths
Longest path in a general graph is NP-hard (it contains Hamiltonian path). In a DAG it is linear. Process vertices in topological order; when you reach , every predecessor has already been finalized, so
The 0 term means "a path may start at "; drop it and initialize sources only if paths must start at a given (then unreachable vertices keep ). Give the example DAG weights A→B 3, A→C 2, B→D 4, C→D 1, D→E 2, F→C 5, F→G 1, G→E 5. In Kahn order A F B C G D E:
| Vertex | Incoming candidates | best | parent |
|---|---|---|---|
| A | (source) | 0 | — |
| F | (source) | 0 | — |
| B | A: 0 + 3 | 3 | A |
| C | A: 0 + 2, F: 0 + 5 | 5 | F |
| G | F: 0 + 1 | 1 | F |
| D | B: 3 + 4, C: 5 + 1 | 7 | B |
| E | D: 7 + 2, G: 1 + 5 | 9 | D |
The longest path has weight 9: follow parents back from E to get A → B → D → E. The same sweep with min instead of max gives single-source shortest paths in a DAG in even with negative edge weights — faster than Dijkstra and immune to the negative-edge problem discussed in Shortest Paths. CLRS section 24.2 calls it DAG-SHORTEST-PATHS.
Counting paths is the same sweep with +: ways[s] = 1, ways[v] = Σ ways[u]. From A, the counts are A 1, B 1, C 1, D 2, E 2 (paths A B D E and A C D E); F and G get 0 because they are not reachable from A. Counts grow exponentially in the number of vertices (a chain of "diamonds" has paths), so problems ask for them modulo .
Critical path scheduling (CPM / PERT)
Give every task a duration and assume unlimited workers. The project cannot finish before the longest (by total duration) chain of dependent tasks completes; that chain is the critical path. Two sweeps compute everything a project manager wants:
- Forward pass, in topological order: earliest start (0 for sources), earliest finish . The project length is .
- Backward pass, in reverse topological order: latest finish ( for sinks), latest start .
- Slack : how long the task can slip without delaying the project. Tasks with zero slack form the critical path(s).
Example project (durations in days, prerequisites in brackets): A spec 2; B schema 3 [A]; C API 5 [B]; D UI 4 [A]; E auth 2 [B]; F integrate 3 [C, D, E]; G docs 1 [D]; H release 1 [F, G].
flowchart LR
A["A spec (2)"] --> B["B schema (3)"]
A --> D["D UI (4)"]
B --> C["C API (5)"]
B --> E["E auth (2)"]
C --> F["F integrate (3)"]
D --> F
E --> F
D --> G["G docs (1)"]
F --> H["H release (1)"]
G --> H
| Task | Duration | ES | EF | LS | LF | Slack |
|---|---|---|---|---|---|---|
| A | 2 | 0 | 2 | 0 | 2 | 0 |
| B | 3 | 2 | 5 | 2 | 5 | 0 |
| C | 5 | 5 | 10 | 5 | 10 | 0 |
| D | 4 | 2 | 6 | 6 | 10 | 4 |
| E | 2 | 5 | 7 | 8 | 10 | 3 |
| F | 3 | 10 | 13 | 10 | 13 | 0 |
| G | 1 | 6 | 7 | 12 | 13 | 6 |
| H | 1 | 13 | 14 | 13 | 14 | 0 |
The project takes 14 days; the critical path is A → B → C → F → H (2 + 3 + 5 + 3 + 1 = 14). The UI work can slip 4 days, the docs 6. Putting more people on the docs cannot shorten the project; shortening the API task can, until another path becomes critical. That is the entire management insight of CPM, developed at DuPont with Remington Rand around 1957, and of PERT, developed for the US Navy's Polaris programme in 1958 (PERT adds probabilistic durations).
Transitive closure in topological order
"Is a prerequisite (direct or indirect) of ?" for many query pairs is a reachability question. In a DAG, process vertices in reverse topological order and set reach[u] = {u} ∪ ⋃ reach[v] over edges u → v. With reach stored as bitsets of bits, each union is word operations, so the closure costs time and bits of memory: for that is about bytes. For (LeetCode "Course Schedule IV") Floyd-Warshall's boolean form, steps, is simpler and fine.
Alien dictionary
You are given words sorted in an unknown alphabet and asked to recover a letter order. Only adjacent pairs carry information, and only their first differing letter: in wrt < wrf, the first difference is t vs f, so t precedes f; nothing after that position says anything. Build one edge per adjacent pair, topologically sort the letters, and report failure on a cycle.
Example: tk, tq, kq, kqe, eqt. The pairs give k → q (tk/tq), t → k (tq/kq), nothing (kq/kqe), k → e (kqe/eqt). Valid alphabets: t k e q and t k q e — the input does not determine the order of e and q, a fact worth saying out loud in an interview.
The prefix edge case: if a word is followed by its own proper prefix (abc then ab), the input is invalid no matter what the alphabet is, because a prefix always sorts first. Many solutions miss this: they find no differing letter, add no edge, and happily return an order. Two more details: include every letter that appears anywhere (even letters with no edges) in the vertex set, and keep in-degrees consistent with the adjacency structure: if adjacency is a set, increment the in-degree only when the edge is new, otherwise a repeated pair such as t → k from two different word pairs counts twice on one side and once on the other, and k never reaches in-degree 0.
The ladder: brute force → better → optimal
Rung 1: try every permutation
Generate all orders and return the first in which every edge points forward. Checking one order is with a position array, so the total is . For that is 3.6 million permutations; for it is . Useless except as a test oracle — which is exactly how the code below uses it, to confirm the count of 21 orders.
Rung 2: repeatedly scan for a source
Keep an in-degree array. Each round, scan all vertices for one that is unprocessed with in-degree 0, output it, and decrement its out-neighbours. Each of the rounds costs for the scan, plus decrements overall: . This is Kahn's idea without the queue. It is fine for , and it is how people often do it by hand.
Why it improves on rung 1: it never backtracks. The proof that "any source can go next" (below) means the first choice is never wrong, so there is nothing to search.
Rung 3: Kahn with a queue, or DFS
The scan in rung 2 rediscovers sources that were already known. A vertex becomes a source at exactly one moment — when its in-degree drops to 0 — so push it into a queue at that moment and never scan. Every vertex is pushed and popped once and every edge is decremented once: . DFS reaches the same bound by a different route: each vertex is coloured gray and black once, each edge examined once.
Why it improves: the scan was per output; the queue makes it amortized. Linear time is optimal, since an algorithm that skips an edge cannot know whether that edge points backwards.
The same ladder for DAG longest path
| Rung | Idea | Time | Why it improves |
|---|---|---|---|
| Enumerate all paths | DFS from every vertex, try every path | Exponential ( paths in stacked diamonds) | — |
| Memoized DFS | best(v) = max over v → w of w + best(w), cache results | Each subproblem solved once; DAG ⇒ no cyclic dependencies between subproblems | |
| Topological sweep | Process in topological order, push values forward | , no recursion | Same work, no stack-depth limit (Python's default recursion limit is 1000) |
Comparison
| Method | Time | Extra space | Detects cycles | Notes |
|---|---|---|---|---|
| All permutations | Yes (none valid) | Test oracle only | ||
| Scan for sources | Yes (count) | Simple, fine for small | ||
| Kahn (queue) | Yes (count ) | Iterative; gives levels; easy to parallelize | ||
| Kahn (min-heap) | Yes | Lexicographically smallest order | ||
| DFS reverse postorder | stack | Yes (gray edge) | Natural when you already run DFS; recursion depth | |
| Subset DP (count orders) | — | Counting is #P-complete in general |
Correctness
Lemma 1: a DAG has a source, and a graph in which every vertex has an incoming edge has a cycle
Suppose every vertex of a finite graph has in-degree at least 1. Start at any , pick an edge , then , and so on. Among (that is names for vertices) some vertex repeats, with , and is a directed cycle. Contrapositive: an acyclic graph has a vertex of in-degree 0. The same argument applied to out-edges shows a DAG also has a sink.
Theorem 2: Kahn outputs all vertices iff the graph is a DAG, and its output is then a topological order
Invariant. At every moment, indeg[v] equals the number of edges whose tail has not yet been popped. True initially (nothing popped). Popping decrements indeg[v] once for each edge , which restores the invariant.
Order is valid. A vertex is pushed only when indeg[v] hits 0, which by the invariant means every predecessor of has already been popped, hence already appended to order. Each vertex is pushed at most once (in-degree hits 0 once and never increases). So for every edge with both endpoints output, appears before .
If the graph is a DAG, everything is output. Suppose the queue empties with a non-empty set of unoutput vertices. No vertex of has in-degree 0, otherwise it would have been pushed when it reached 0 (or initially). By the invariant, every has an incoming edge from an unpopped vertex, i.e. from . So the subgraph induced by has every in-degree , and by Lemma 1 it contains a cycle — contradicting acyclicity.
If the graph has a cycle, not everything is output. Let be a cycle and suppose all its vertices were output. Look at the first vertex to be popped. Its predecessor on the cycle, , is in and had not been popped yet, so indeg[c] when was pushed — impossible. Hence some cycle vertex is never output, and len(order) < V.
The same argument shows something useful for debugging: the unoutput vertices are exactly those that lie on a cycle or are reachable from one.
Theorem 3: in a DAG, DFS finishes before for every edge
Consider the moment DFS examines edge (while is gray). Three cases:
- is white. Then is visited now, as a descendant of , and the recursive call on returns — so finishes — before finishes. .
- is black. Then has already finished and has not. .
- is gray. Gray vertices are exactly those on the current recursion stack, so is an ancestor of and the stack contains a path . Together with that is a cycle, impossible in a DAG.
So every edge goes from larger finishing time to smaller, and listing vertices by decreasing finishing time (reverse postorder) puts every edge forward.
Conversely, if the graph has a cycle, DFS always meets a gray vertex. Let be the first vertex of the cycle to be discovered, and its predecessor on the cycle. At 's discovery the rest of the cycle is white and reachable from along white vertices, so by the white-path theorem (CLRS Theorem 22.9) becomes a descendant of , and when DFS examines , is still gray. That is why "edge to gray ⇒ cycle" is both sound and complete.
Theorem 4: the DAG DP computes longest paths
Claim: when vertex is reached in topological order, best[v] equals the maximum weight of a path ending at . Induction on position. A path ending at is either just (weight 0) or a path ending at some predecessor followed by the edge . Every predecessor precedes in the order, so by the induction hypothesis best[u] was already final when was processed, and processing relaxed best[v] with best[u] + w(u, v). Taking the maximum over all predecessors and 0 is exactly the recurrence. Nothing can change best[v] after is processed, because no vertex after has an edge into .
This proof uses one property only: when a vertex is processed, all its in-edges have already been processed. That is the general contract of DP — subproblems are solved before the problems that use them — and a topological order of the subproblem graph is precisely an order that satisfies it.
Why the lexicographic greedy is optimal
Let be the set of sources of the remaining graph. Every topological order of the remaining graph starts with an element of (its first element has no remaining predecessors). Every element starts at least one (remove it; the rest is a DAG; append any topological order of the rest). So the lexicographically smallest order starts with , and after removing it the same argument applies.
Complexity
| Operation | Time | Space |
|---|---|---|
| Kahn (queue) | beyond the adjacency list | |
| DFS topological sort | (colours and stack) | |
| Kahn with min-heap | ||
| DAG longest / shortest path, path counts | ||
| Critical path (two passes) | ||
| Transitive closure with bitsets | , | words |
| Counting topological orders (subset DP) |
There is no best/average/worst distinction for Kahn or DFS: they always touch every vertex and edge exactly once. Building the adjacency list from an edge list is itself ; if the input arrives as an adjacency matrix, every algorithm here becomes because reading the matrix is.
Constants: Kahn on a CSR (compressed sparse row) adjacency array is a sequential scan of each vertex's out-edges plus random writes into indeg, which is about as cache-friendly as graph algorithms get. The recursive DFS is the one to watch: on a path of vertices it recurses deep, which overflows Python's default recursion limit (1000) and can overflow a default 1 MB thread stack in C++ or Java. The implementations below use an explicit stack.
Implementation
Kahn and DFS with cycle detection
Vertices are 0..n-1, edges are (u, v) pairs meaning u before v. kahn returns the order it managed to produce, which is shorter than n exactly when there is a cycle; dfsTopo returns None/null on a cycle. Tests use the running example with A..G = 0..6.
from collections import deque
from itertools import permutations
def kahn(n: int, edges: list[tuple[int, int]]) -> list[int]:
"""Topological order of 0..n-1. Shorter than n exactly when the graph has a cycle."""
adj: list[list[int]] = [[] for _ in range(n)]
indeg = [0] * n
for u, v in edges:
adj[u].append(v)
indeg[v] += 1
q = deque(v for v in range(n) if indeg[v] == 0)
order: list[int] = []
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order
def dfs_topo(n: int, edges: list[tuple[int, int]]) -> list[int] | None:
"""Reverse postorder of an iterative DFS; None if a back edge (cycle) is found."""
adj: list[list[int]] = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n
nxt = [0] * n # next out-edge to examine, per vertex
post: list[int] = []
for root in range(n):
if color[root] != WHITE:
continue
color[root] = GRAY
stack = [root]
while stack:
u = stack[-1]
if nxt[u] < len(adj[u]):
v = adj[u][nxt[u]]
nxt[u] += 1
if color[v] == GRAY:
return None # back edge: v is an ancestor of u
if color[v] == WHITE:
color[v] = GRAY
stack.append(v)
else:
stack.pop()
color[u] = BLACK
post.append(u)
post.reverse()
return post
def is_topological(order: list[int], n: int, edges: list[tuple[int, int]]) -> bool:
if sorted(order) != list(range(n)):
return False
pos = [0] * n
for i, v in enumerate(order):
pos[v] = i
return all(pos[u] < pos[v] for u, v in edges)
A, B, C, D, E, F, G = range(7)
EDGES = [(A, B), (A, C), (B, D), (C, D), (D, E), (F, C), (F, G), (G, E)]
assert kahn(7, EDGES) == [A, F, B, C, G, D, E]
assert dfs_topo(7, EDGES) == [F, G, A, C, B, D, E]
assert is_topological(kahn(7, EDGES), 7, EDGES)
assert sum(is_topological(list(p), 7, EDGES) for p in permutations(range(7))) == 21
cyclic = EDGES + [(E, C)] # closes C -> D -> E -> C
assert kahn(7, cyclic) == [A, F, B, G] # 4 < 7: cycle
assert dfs_topo(7, cyclic) is None
assert kahn(1, [(0, 0)]) == [] and dfs_topo(1, [(0, 0)]) is None # self-loop
assert kahn(0, []) == [] and dfs_topo(0, []) == []
chain = [(i, i + 1) for i in range(99_999)] # deep: no recursion limit hit
assert dfs_topo(100_000, chain) == list(range(100_000))
print("topological sort ok")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class TopoSort {
static List<List<Integer>> build(int n, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) adj.get(e[0]).add(e[1]);
return adj;
}
/** Topological order of 0..n-1; shorter than n exactly when there is a cycle. */
static int[] kahn(int n, int[][] edges) {
List<List<Integer>> adj = build(n, edges);
int[] indeg = new int[n];
for (int[] e : edges) indeg[e[1]]++;
ArrayDeque<Integer> q = new ArrayDeque<>();
for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);
int[] order = new int[n];
int k = 0;
while (!q.isEmpty()) {
int u = q.poll();
order[k++] = u;
for (int v : adj.get(u)) if (--indeg[v] == 0) q.add(v);
}
return Arrays.copyOf(order, k);
}
/** Reverse postorder of an iterative DFS; null if a back edge (cycle) is found. */
static int[] dfsTopo(int n, int[][] edges) {
List<List<Integer>> adj = build(n, edges);
int[] color = new int[n]; // 0 white, 1 gray, 2 black
int[] next = new int[n];
int[] stack = new int[n]; // each vertex is pushed at most once
int[] post = new int[n];
int k = 0;
for (int root = 0; root < n; root++) {
if (color[root] != 0) continue;
int top = 0;
stack[top++] = root;
color[root] = 1;
while (top > 0) {
int u = stack[top - 1];
if (next[u] < adj.get(u).size()) {
int v = adj.get(u).get(next[u]++);
if (color[v] == 1) return null;
if (color[v] == 0) { color[v] = 1; stack[top++] = v; }
} else {
top--;
color[u] = 2;
post[k++] = u;
}
}
}
int[] order = new int[n];
for (int i = 0; i < n; i++) order[i] = post[n - 1 - i];
return order;
}
static boolean isTopological(int[] order, int n, int[][] edges) {
if (order.length != n) return false;
int[] pos = new int[n];
Arrays.fill(pos, -1);
for (int i = 0; i < n; i++) { if (pos[order[i]] != -1) return false; pos[order[i]] = i; }
for (int[] e : edges) if (pos[e[0]] >= pos[e[1]]) return false;
return true;
}
static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }
public static void main(String[] args) {
int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {5, 2}, {5, 6}, {6, 4}};
check(Arrays.equals(kahn(7, edges), new int[]{0, 5, 1, 2, 6, 3, 4}), "kahn");
check(Arrays.equals(dfsTopo(7, edges), new int[]{5, 6, 0, 2, 1, 3, 4}), "dfs");
check(isTopological(kahn(7, edges), 7, edges), "valid");
int[][] cyclic = Arrays.copyOf(edges, edges.length + 1);
cyclic[edges.length] = new int[]{4, 2};
check(Arrays.equals(kahn(7, cyclic), new int[]{0, 5, 1, 6}), "kahn cycle");
check(dfsTopo(7, cyclic) == null, "dfs cycle");
check(kahn(1, new int[][]{{0, 0}}).length == 0 && dfsTopo(1, new int[][]{{0, 0}}) == null, "self-loop");
check(kahn(0, new int[0][]).length == 0 && dfsTopo(0, new int[0][]).length == 0, "empty");
int m = 100_000;
int[][] chain = new int[m - 1][];
for (int i = 0; i + 1 < m; i++) chain[i] = new int[]{i, i + 1};
int[] deep = dfsTopo(m, chain);
for (int i = 0; i < m; i++) check(deep[i] == i, "chain");
System.out.println("topological sort ok");
}
}
#include <cassert>
#include <deque>
#include <iostream>
#include <optional>
#include <utility>
#include <vector>
using Edges = std::vector<std::pair<int, int>>;
std::vector<std::vector<int>> build(int n, const Edges& edges) {
std::vector<std::vector<int>> adj(n);
for (auto [u, v] : edges) adj[u].push_back(v);
return adj;
}
// Topological order of 0..n-1; shorter than n exactly when there is a cycle.
std::vector<int> kahn(int n, const Edges& edges) {
auto adj = build(n, edges);
std::vector<int> indeg(n, 0), order;
for (auto [u, v] : edges) ++indeg[v];
std::deque<int> q;
for (int v = 0; v < n; ++v) if (indeg[v] == 0) q.push_back(v);
while (!q.empty()) {
int u = q.front();
q.pop_front();
order.push_back(u);
for (int v : adj[u]) if (--indeg[v] == 0) q.push_back(v);
}
return order;
}
// Reverse postorder of an iterative DFS; nullopt if a back edge (cycle) is found.
std::optional<std::vector<int>> dfs_topo(int n, const Edges& edges) {
auto adj = build(n, edges);
std::vector<int> color(n, 0), next(n, 0), post, stack; // 0 white, 1 gray, 2 black
for (int root = 0; root < n; ++root) {
if (color[root] != 0) continue;
color[root] = 1;
stack.push_back(root);
while (!stack.empty()) {
int u = stack.back();
if (next[u] < static_cast<int>(adj[u].size())) {
int v = adj[u][next[u]++];
if (color[v] == 1) return std::nullopt;
if (color[v] == 0) { color[v] = 1; stack.push_back(v); }
} else {
stack.pop_back();
color[u] = 2;
post.push_back(u);
}
}
}
return std::vector<int>(post.rbegin(), post.rend());
}
bool is_topological(const std::vector<int>& order, int n, const Edges& edges) {
if (static_cast<int>(order.size()) != n) return false;
std::vector<int> pos(n, -1);
for (int i = 0; i < n; ++i) { if (pos[order[i]] != -1) return false; pos[order[i]] = i; }
for (auto [u, v] : edges) if (pos[u] >= pos[v]) return false;
return true;
}
int main() {
Edges edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {5, 2}, {5, 6}, {6, 4}};
assert((kahn(7, edges) == std::vector<int>{0, 5, 1, 2, 6, 3, 4}));
assert((dfs_topo(7, edges).value() == std::vector<int>{5, 6, 0, 2, 1, 3, 4}));
assert(is_topological(kahn(7, edges), 7, edges));
Edges cyclic = edges;
cyclic.push_back({4, 2});
assert((kahn(7, cyclic) == std::vector<int>{0, 5, 1, 6}));
assert(!dfs_topo(7, cyclic).has_value());
assert(kahn(1, {{0, 0}}).empty() && !dfs_topo(1, {{0, 0}}).has_value());
assert(kahn(0, {}).empty() && dfs_topo(0, {}).value().empty());
const int m = 100000;
Edges chain;
for (int i = 0; i + 1 < m; ++i) chain.push_back({i, i + 1});
auto deep = dfs_topo(m, chain).value();
for (int i = 0; i < m; ++i) assert(deep[i] == i);
std::cout << "topological sort ok\n";
}
type Edge = [number, number];
function build(n: number, edges: Edge[]): number[][] {
const adj: number[][] = Array.from({ length: n }, () => []);
for (const [u, v] of edges) adj[u].push(v);
return adj;
}
// Topological order of 0..n-1; shorter than n exactly when there is a cycle.
function kahn(n: number, edges: Edge[]): number[] {
const adj = build(n, edges);
const indeg = new Array<number>(n).fill(0);
for (const [, v] of edges) indeg[v]++;
const q: number[] = [];
for (let v = 0; v < n; v++) if (indeg[v] === 0) q.push(v);
let head = 0; // array + head index = O(1) queue
while (head < q.length) {
const u = q[head++];
for (const v of adj[u]) if (--indeg[v] === 0) q.push(v);
}
return q; // q holds every popped vertex, in order
}
// Reverse postorder of an iterative DFS; null if a back edge (cycle) is found.
function dfsTopo(n: number, edges: Edge[]): number[] | null {
const adj = build(n, edges);
const color = new Array<number>(n).fill(0); // 0 white, 1 gray, 2 black
const next = new Array<number>(n).fill(0);
const post: number[] = [];
for (let root = 0; root < n; root++) {
if (color[root] !== 0) continue;
color[root] = 1;
const stack = [root];
while (stack.length > 0) {
const u = stack[stack.length - 1];
if (next[u] < adj[u].length) {
const v = adj[u][next[u]++];
if (color[v] === 1) return null;
if (color[v] === 0) { color[v] = 1; stack.push(v); }
} else {
stack.pop();
color[u] = 2;
post.push(u);
}
}
}
return post.reverse();
}
function isTopological(order: number[], n: number, edges: Edge[]): boolean {
if (order.length !== n) return false;
const pos = new Array<number>(n).fill(-1);
for (let i = 0; i < n; i++) { if (pos[order[i]] !== -1) return false; pos[order[i]] = i; }
return edges.every(([u, v]) => pos[u] < pos[v]);
}
function check(ok: boolean, what: string): void { if (!ok) throw new Error(what); }
const same = (a: number[] | null, b: number[]) => a !== null && a.length === b.length && a.every((x, i) => x === b[i]);
const edges: Edge[] = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [5, 2], [5, 6], [6, 4]];
check(same(kahn(7, edges), [0, 5, 1, 2, 6, 3, 4]), "kahn");
check(same(dfsTopo(7, edges), [5, 6, 0, 2, 1, 3, 4]), "dfs");
check(isTopological(kahn(7, edges), 7, edges), "valid");
const cyclic: Edge[] = [...edges, [4, 2]];
check(same(kahn(7, cyclic), [0, 5, 1, 6]), "kahn cycle");
check(dfsTopo(7, cyclic) === null, "dfs cycle");
check(kahn(1, [[0, 0]]).length === 0 && dfsTopo(1, [[0, 0]]) === null, "self-loop");
check(kahn(0, []).length === 0 && same(dfsTopo(0, []), []), "empty");
const m = 100_000;
const chain: Edge[] = Array.from({ length: m - 1 }, (_, i) => [i, i + 1] as Edge);
check(same(dfsTopo(m, chain), Array.from({ length: m }, (_, i) => i)), "chain");
console.log("topological sort ok");
DAG DP: longest path with reconstruction, and path counting
longestPath returns the maximum path weight (a path may start anywhere) and one path achieving it; countPaths counts paths modulo . Both raise on a cycle. The second test stacks 30 diamonds, which has paths, .
from collections import deque
MOD = 1_000_000_007
def topo_order(n: int, adj: list[list[int]]) -> list[int]:
indeg = [0] * n
for u in range(n):
for v in adj[u]:
indeg[v] += 1
q = deque(v for v in range(n) if indeg[v] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
if len(order) < n:
raise ValueError("graph has a cycle")
return order
def longest_path(n: int, edges: list[tuple[int, int, int]]) -> tuple[int, list[int]]:
adj: list[list[int]] = [[] for _ in range(n)]
wadj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
for u, v, w in edges:
adj[u].append(v)
wadj[u].append((v, w))
best = [0] * n # best path weight ending at v (a path may start at v)
parent = [-1] * n
for u in topo_order(n, adj):
for v, w in wadj[u]:
if best[u] + w > best[v]:
best[v] = best[u] + w
parent[v] = u
end = max(range(n), key=best.__getitem__)
path = []
while end != -1:
path.append(end)
end = parent[end]
return best[path[0]], path[::-1]
def count_paths(n: int, edges: list[tuple[int, int]], s: int, t: int) -> int:
adj: list[list[int]] = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
ways = [0] * n
ways[s] = 1
for u in topo_order(n, adj):
if ways[u]:
for v in adj[u]:
ways[v] = (ways[v] + ways[u]) % MOD
return ways[t]
A, B, C, D, E, F, G = range(7)
W = [(A, B, 3), (A, C, 2), (B, D, 4), (C, D, 1), (D, E, 2), (F, C, 5), (F, G, 1), (G, E, 5)]
assert longest_path(7, W) == (9, [A, B, D, E])
plain = [(u, v) for u, v, _ in W]
assert count_paths(7, plain, A, E) == 2 and count_paths(7, plain, F, E) == 2
assert count_paths(7, plain, A, F) == 0
k = 30 # diamonds: c_i -> x_i -> c_{i+1}, c_i -> y_i -> c_{i+1}
dia = []
for i in range(k):
x, y = k + 1 + 2 * i, k + 2 + 2 * i
dia += [(i, x), (x, i + 1), (i, y), (y, i + 1)]
assert count_paths(3 * k + 1, dia, 0, k) == pow(2, k, MOD) == 73_741_817
try:
longest_path(2, [(0, 1, 1), (1, 0, 1)])
raise AssertionError("cycle not detected")
except ValueError:
pass
print("dag dp ok")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class DagDp {
static final long MOD = 1_000_000_007L;
static int[] topoOrder(int n, List<List<int[]>> adj) {
int[] indeg = new int[n];
for (List<int[]> out : adj) for (int[] e : out) indeg[e[0]]++;
ArrayDeque<Integer> q = new ArrayDeque<>();
for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);
int[] order = new int[n];
int k = 0;
while (!q.isEmpty()) {
int u = q.poll();
order[k++] = u;
for (int[] e : adj.get(u)) if (--indeg[e[0]] == 0) q.add(e[0]);
}
if (k < n) throw new IllegalArgumentException("graph has a cycle");
return order;
}
static List<List<int[]>> build(int n, int[][] edges) { // edge = {u, v, w}; w ignored if absent
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) adj.get(e[0]).add(new int[]{e[1], e.length > 2 ? e[2] : 0});
return adj;
}
/** Returns {weight, v0, v1, ...}: the best weight followed by one longest path. */
static long[] longestPath(int n, int[][] edges) {
List<List<int[]>> adj = build(n, edges);
long[] best = new long[n];
int[] parent = new int[n];
Arrays.fill(parent, -1);
for (int u : topoOrder(n, adj))
for (int[] e : adj.get(u))
if (best[u] + e[1] > best[e[0]]) { best[e[0]] = best[u] + e[1]; parent[e[0]] = u; }
int end = 0;
for (int v = 1; v < n; v++) if (best[v] > best[end]) end = v;
List<Long> path = new ArrayList<>();
for (int v = end; v != -1; v = parent[v]) path.add(0, (long) v);
long[] out = new long[path.size() + 1];
out[0] = best[end];
for (int i = 0; i < path.size(); i++) out[i + 1] = path.get(i);
return out;
}
static long countPaths(int n, int[][] edges, int s, int t) {
List<List<int[]>> adj = build(n, edges);
long[] ways = new long[n];
ways[s] = 1;
for (int u : topoOrder(n, adj))
if (ways[u] != 0)
for (int[] e : adj.get(u)) ways[e[0]] = (ways[e[0]] + ways[u]) % MOD;
return ways[t];
}
static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }
public static void main(String[] args) {
int[][] w = {{0, 1, 3}, {0, 2, 2}, {1, 3, 4}, {2, 3, 1}, {3, 4, 2}, {5, 2, 5}, {5, 6, 1}, {6, 4, 5}};
check(Arrays.equals(longestPath(7, w), new long[]{9, 0, 1, 3, 4}), "longest");
check(countPaths(7, w, 0, 4) == 2 && countPaths(7, w, 5, 4) == 2 && countPaths(7, w, 0, 5) == 0, "count");
int k = 30;
int[][] dia = new int[4 * k][];
for (int i = 0; i < k; i++) {
int x = k + 1 + 2 * i, y = k + 2 + 2 * i;
dia[4 * i] = new int[]{i, x};
dia[4 * i + 1] = new int[]{x, i + 1};
dia[4 * i + 2] = new int[]{i, y};
dia[4 * i + 3] = new int[]{y, i + 1};
}
check(countPaths(3 * k + 1, dia, 0, k) == 73_741_817L, "diamonds");
boolean threw = false;
try { longestPath(2, new int[][]{{0, 1, 1}, {1, 0, 1}}); } catch (IllegalArgumentException ex) { threw = true; }
check(threw, "cycle");
System.out.println("dag dp ok");
}
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <deque>
#include <iostream>
#include <stdexcept>
#include <utility>
#include <vector>
constexpr std::int64_t MOD = 1'000'000'007;
struct Edge { int u, v; std::int64_t w; };
using Adj = std::vector<std::vector<std::pair<int, std::int64_t>>>;
Adj build(int n, const std::vector<Edge>& edges) {
Adj adj(n);
for (const auto& e : edges) adj[e.u].push_back({e.v, e.w});
return adj;
}
std::vector<int> topo_order(int n, const Adj& adj) {
std::vector<int> indeg(n, 0), order;
for (const auto& out : adj) for (auto [v, w] : out) ++indeg[v];
std::deque<int> q;
for (int v = 0; v < n; ++v) if (indeg[v] == 0) q.push_back(v);
while (!q.empty()) {
int u = q.front();
q.pop_front();
order.push_back(u);
for (auto [v, w] : adj[u]) if (--indeg[v] == 0) q.push_back(v);
}
if (static_cast<int>(order.size()) < n) throw std::invalid_argument("graph has a cycle");
return order;
}
std::pair<std::int64_t, std::vector<int>> longest_path(int n, const std::vector<Edge>& edges) {
Adj adj = build(n, edges);
std::vector<std::int64_t> best(n, 0);
std::vector<int> parent(n, -1);
for (int u : topo_order(n, adj))
for (auto [v, w] : adj[u])
if (best[u] + w > best[v]) { best[v] = best[u] + w; parent[v] = u; }
int end = static_cast<int>(std::max_element(best.begin(), best.end()) - best.begin());
std::vector<int> path;
for (int v = end; v != -1; v = parent[v]) path.push_back(v);
std::reverse(path.begin(), path.end());
return {best[end], path};
}
std::int64_t count_paths(int n, const std::vector<Edge>& edges, int s, int t) {
Adj adj = build(n, edges);
std::vector<std::int64_t> ways(n, 0);
ways[s] = 1;
for (int u : topo_order(n, adj))
if (ways[u])
for (auto [v, w] : adj[u]) ways[v] = (ways[v] + ways[u]) % MOD;
return ways[t];
}
int main() {
std::vector<Edge> w = {{0, 1, 3}, {0, 2, 2}, {1, 3, 4}, {2, 3, 1}, {3, 4, 2}, {5, 2, 5}, {5, 6, 1}, {6, 4, 5}};
auto [best, path] = longest_path(7, w);
assert(best == 9 && (path == std::vector<int>{0, 1, 3, 4}));
assert(count_paths(7, w, 0, 4) == 2 && count_paths(7, w, 5, 4) == 2 && count_paths(7, w, 0, 5) == 0);
const int k = 30;
std::vector<Edge> dia;
for (int i = 0; i < k; ++i) {
int x = k + 1 + 2 * i, y = k + 2 + 2 * i;
dia.insert(dia.end(), {{i, x, 0}, {x, i + 1, 0}, {i, y, 0}, {y, i + 1, 0}});
}
assert(count_paths(3 * k + 1, dia, 0, k) == 73741817);
bool threw = false;
try { longest_path(2, {{0, 1, 1}, {1, 0, 1}}); } catch (const std::invalid_argument&) { threw = true; }
assert(threw);
std::cout << "dag dp ok\n";
}
const MOD = 1_000_000_007n;
type WEdge = [number, number, number];
function build(n: number, edges: WEdge[]): [number, number][][] {
const adj: [number, number][][] = Array.from({ length: n }, () => []);
for (const [u, v, w] of edges) adj[u].push([v, w]);
return adj;
}
function topoOrder(n: number, adj: [number, number][][]): number[] {
const indeg = new Array<number>(n).fill(0);
for (const out of adj) for (const [v] of out) indeg[v]++;
const q: number[] = [];
for (let v = 0; v < n; v++) if (indeg[v] === 0) q.push(v);
for (let head = 0; head < q.length; head++)
for (const [v] of adj[q[head]]) if (--indeg[v] === 0) q.push(v);
if (q.length < n) throw new Error("graph has a cycle");
return q;
}
function longestPath(n: number, edges: WEdge[]): [number, number[]] {
const adj = build(n, edges);
const best = new Array<number>(n).fill(0);
const parent = new Array<number>(n).fill(-1);
for (const u of topoOrder(n, adj))
for (const [v, w] of adj[u])
if (best[u] + w > best[v]) { best[v] = best[u] + w; parent[v] = u; }
let end = 0;
for (let v = 1; v < n; v++) if (best[v] > best[end]) end = v;
const path: number[] = [];
for (let v = end; v !== -1; v = parent[v]) path.push(v);
return [best[end], path.reverse()];
}
function countPaths(n: number, edges: WEdge[], s: number, t: number): bigint {
const adj = build(n, edges);
const ways = new Array<bigint>(n).fill(0n); // bigint: sums of two values near 1e9 stay exact
ways[s] = 1n;
for (const u of topoOrder(n, adj))
if (ways[u] !== 0n) for (const [v] of adj[u]) ways[v] = (ways[v] + ways[u]) % MOD;
return ways[t];
}
function check(ok: boolean, what: string): void { if (!ok) throw new Error(what); }
const w: WEdge[] = [[0, 1, 3], [0, 2, 2], [1, 3, 4], [2, 3, 1], [3, 4, 2], [5, 2, 5], [5, 6, 1], [6, 4, 5]];
const [best, path] = longestPath(7, w);
check(best === 9 && path.join(",") === "0,1,3,4", "longest");
check(countPaths(7, w, 0, 4) === 2n && countPaths(7, w, 5, 4) === 2n && countPaths(7, w, 0, 5) === 0n, "count");
const k = 30;
const dia: WEdge[] = [];
for (let i = 0; i < k; i++) {
const x = k + 1 + 2 * i, y = k + 2 + 2 * i;
dia.push([i, x, 0], [x, i + 1, 0], [i, y, 0], [y, i + 1, 0]);
}
check(countPaths(3 * k + 1, dia, 0, k) === 73_741_817n, "diamonds");
let threw = false;
try { longestPath(2, [[0, 1, 1], [1, 0, 1]]); } catch { threw = true; }
check(threw, "cycle");
console.log("dag dp ok");
In TypeScript, number holds integers exactly only up to , and would overflow that, but path counting only ever adds two residues, so number would actually suffice here; bigint is used to make the arithmetic obviously safe if you later multiply.
Variant: lexicographically smallest order, and "smallest labels first"
import heapq
def lexicographic_topo(n: int, edges: list[tuple[int, int]]) -> list[int] | None:
adj: list[list[int]] = [[] for _ in range(n)]
indeg = [0] * n
for u, v in edges:
adj[u].append(v)
indeg[v] += 1
heap = [v for v in range(n) if indeg[v] == 0]
heapq.heapify(heap)
order = []
while heap:
u = heapq.heappop(heap)
order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
heapq.heappush(heap, v)
return order if len(order) == n else None
def smallest_labels_first(n: int, edges: list[tuple[int, int]]) -> list[int] | None:
"""Minimise the position of 0, then of 1, ...: Kahn on the reversed graph with a max-heap."""
radj: list[list[int]] = [[] for _ in range(n)]
outdeg = [0] * n
for u, v in edges:
radj[v].append(u)
outdeg[u] += 1
heap = [-v for v in range(n) if outdeg[v] == 0]
heapq.heapify(heap)
rev = []
while heap:
v = -heapq.heappop(heap)
rev.append(v)
for u in radj[v]:
outdeg[u] -= 1
if outdeg[u] == 0:
heapq.heappush(heap, -u)
return rev[::-1] if len(rev) == n else None
A, B, C, D, E, F, G = range(7)
EDGES = [(A, B), (A, C), (B, D), (C, D), (D, E), (F, C), (F, G), (G, E)]
assert lexicographic_topo(7, EDGES) == [A, B, F, C, D, G, E]
# 0-based version of the page's example: labels 1, 2, 3 -> 0, 1, 2 and the edge 3 -> 1 becomes 2 -> 0
assert lexicographic_topo(3, [(2, 0)]) == [1, 2, 0] # vertex 0 lands last
assert smallest_labels_first(3, [(2, 0)]) == [2, 0, 1] # vertex 0 as early as possible
assert lexicographic_topo(2, [(0, 1), (1, 0)]) is None
print("lexicographic variants ok")
Variant: count topological orders, minimum rounds, critical path
from collections import deque
def count_orders(n: int, edges: list[tuple[int, int]]) -> int:
pred = [0] * n
for u, v in edges:
pred[v] |= 1 << u
ways = [0] * (1 << n)
ways[0] = 1
for mask in range(1 << n):
if ways[mask]:
for v in range(n):
if not mask >> v & 1 and pred[v] & mask == pred[v]:
ways[mask | 1 << v] += ways[mask]
return ways[-1]
def min_rounds(n: int, edges: list[tuple[int, int]]) -> int:
"""Unlimited tasks per round; -1 if there is a cycle."""
adj: list[list[int]] = [[] for _ in range(n)]
indeg = [0] * n
for u, v in edges:
adj[u].append(v)
indeg[v] += 1
level = deque(v for v in range(n) if indeg[v] == 0)
rounds = done = 0
while level:
rounds += 1
nxt = deque()
for u in level:
done += 1
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
nxt.append(v)
level = nxt
return rounds if done == n else -1
def critical_path(dur: dict[str, int], pre: dict[str, list[str]]) -> tuple[int, dict[str, tuple[int, int, int, int, int]]]:
"""Returns (T, {task: (ES, EF, LS, LF, slack)}). `dur` must list tasks in a topological order."""
order = list(dur)
es, ef = {}, {}
for x in order:
es[x] = max((ef[p] for p in pre.get(x, [])), default=0)
ef[x] = es[x] + dur[x]
T = max(ef.values())
succ: dict[str, list[str]] = {x: [] for x in order}
for x in order:
for p in pre.get(x, []):
succ[p].append(x)
ls, lf = {}, {}
for x in reversed(order):
lf[x] = min((ls[s] for s in succ[x]), default=T)
ls[x] = lf[x] - dur[x]
return T, {x: (es[x], ef[x], ls[x], lf[x], ls[x] - es[x]) for x in order}
A, B, C, D, E, F, G = range(7)
EDGES = [(A, B), (A, C), (B, D), (C, D), (D, E), (F, C), (F, G), (G, E)]
assert count_orders(7, EDGES) == 21
assert count_orders(4, []) == 24 # no constraints: 4!
assert min_rounds(7, EDGES) == 4
assert min_rounds(2, [(0, 1), (1, 0)]) == -1
dur = {"A": 2, "B": 3, "C": 5, "D": 4, "E": 2, "F": 3, "G": 1, "H": 1}
pre = {"B": ["A"], "C": ["B"], "D": ["A"], "E": ["B"], "F": ["C", "D", "E"], "G": ["D"], "H": ["F", "G"]}
T, table = critical_path(dur, pre)
assert T == 14
assert table["D"] == (2, 6, 6, 10, 4) and table["E"] == (5, 7, 8, 10, 3) and table["G"] == (6, 7, 12, 13, 6)
assert [x for x in dur if table[x][4] == 0] == ["A", "B", "C", "F", "H"]
print("counting, rounds, critical path ok")
Variant: alien dictionary and prerequisite queries
import heapq
def alien_order(words: list[str]) -> str:
"""One valid alphabet (smallest letter first among ties), or "" if the input is inconsistent."""
letters = sorted({c for w in words for c in w})
adj: dict[str, set[str]] = {c: set() for c in letters}
indeg = {c: 0 for c in letters}
for a, b in zip(words, words[1:]):
for x, y in zip(a, b):
if x != y:
if y not in adj[x]: # count each distinct edge once
adj[x].add(y)
indeg[y] += 1
break
else:
if len(a) > len(b): # "abc" before "ab": no alphabet can do that
return ""
heap = [c for c in letters if indeg[c] == 0]
heapq.heapify(heap)
out = []
while heap:
c = heapq.heappop(heap)
out.append(c)
for y in adj[c]:
indeg[y] -= 1
if indeg[y] == 0:
heapq.heappush(heap, y)
return "".join(out) if len(out) == len(letters) else ""
def prerequisite_queries(n: int, edges: list[tuple[int, int]], queries: list[tuple[int, int]]) -> list[bool]:
"""reach[u] as a Python int bitset, filled in reverse topological order."""
adj: list[list[int]] = [[] for _ in range(n)]
indeg = [0] * n
for u, v in edges:
adj[u].append(v)
indeg[v] += 1
order = [v for v in range(n) if indeg[v] == 0]
for u in order: # Kahn, using the list itself as the queue
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
order.append(v)
reach = [1 << v for v in range(n)]
for u in reversed(order):
for v in adj[u]:
reach[u] |= reach[v]
return [u != v and bool(reach[u] >> v & 1) for u, v in queries]
assert alien_order(["tk", "tq", "kq", "kqe", "eqt"]) == "tkeq"
assert alien_order(["wrt", "wrf", "er", "ett", "rftt"]) == "wertf"
assert alien_order(["abc", "ab"]) == "" # prefix after its extension
assert alien_order(["a", "b", "a"]) == "" # a < b and b < a: cycle
assert alien_order(["z"]) == "z"
assert prerequisite_queries(4, [(0, 1), (1, 2), (2, 3)], [(0, 3), (3, 0), (1, 1)]) == [True, False, False]
print("alien dictionary, closure ok")
Real-world uses
Build systems. A build is a DAG: targets depend on other targets and on source files. make reads rules of the form target: prerequisites, walks the dependency graph from the requested goal, and rebuilds a target only after its prerequisites are up to date (and only if one of them is newer). With make -j N it runs up to N independent recipes at once, which is level-by-level Kahn with a worker limit. GNU make reports a "circular dependency dropped" warning when it finds a cycle. Bazel builds an explicit action graph from BUILD files and executes actions once their inputs are available, in parallel and, optionally, remotely; it also rejects dependency cycles among targets. The details of each tool's scheduler differ (and are not all documented), but the contract is the same: an action runs only after every action that produces its inputs.
Package managers. Installing a package means installing its dependencies first, and their dependencies before them: a topological order of the dependency graph. Real dependency graphs are not always acyclic — npm allows packages that depend on each other, and Node's module loader tolerates circular requires by handing out a partially initialized module — so tools that need an order typically break or group cycles rather than refuse them. Version resolution (choosing which version of each package) is a separate and much harder problem, NP-complete in general for constraint languages like npm's or Debian's; the topological part comes after the versions are chosen.
Standard libraries and command-line tools. Python ships graphlib.TopologicalSorter (since 3.9). Its prepare() / get_ready() / done() interface is Kahn's algorithm turned inside out for parallel execution: get_ready() returns every node whose predecessors are done, you hand them to workers, and calling done(node) decrements in-degrees and makes new nodes ready. It raises CycleError with an example cycle. POSIX specifies a tsort utility that reads pairs of items and prints a total order.
Workflow engines and data pipelines. Apache Airflow calls each workflow a "DAG" in its API: tasks are vertices, dependencies are edges, and the scheduler starts a task when its upstream tasks have succeeded. Spark's scheduler splits a job into stages that form a DAG and submits a stage when its parent stages are complete. dbt orders SQL models by their ref() dependencies. Any of these refusing to start because of a "cycle detected" error is Kahn's len(order) < V check.
Spreadsheets. Each formula cell depends on the cells it references. Recalculation must evaluate a cell after its inputs, and a reference cycle is reported as a "circular reference" error. Production spreadsheet engines maintain this ordering incrementally rather than re-sorting the whole sheet on every edit; the exact mechanism is implementation-specific.
Compilers and databases. Instruction schedulers order the instructions of a basic block along the data-dependence DAG (an instruction cannot issue before the instructions producing its operands), choosing among ready instructions with heuristics such as "longest path to the end of the block" — the critical-path idea at the scale of nanoseconds. Database dump tools must create tables, types and constraints so that referenced objects exist first; PostgreSQL's pg_dump, for example, sorts its dumpable objects by their dependencies. Foreign-key relationships among tables form a graph whose topological order is a safe load order (and whose cycles are why dump tools add foreign-key constraints after loading data). See How Databases Work and The Relational Model.
Operating systems and schedulers. Service managers start services after the services they are ordered after; task schedulers with dependencies (see CPU Scheduling) and deadlock detection both reason about directed graphs: a wait-for graph with a cycle is a deadlock, and detecting it is exactly the gray-edge check (OS Algorithms).
Project management. CPM and PERT, described above, are still the core of tools that draw Gantt charts with a "critical path" highlight. The two-pass ES/LS computation in the variants section is the algorithm.
Pitfalls & edge cases
- Edge direction. "Course
ahas prerequisiteb" is the edgeb → a. Getting it backwards produces a reversed order that passes cycle-detection tests and fails every ordering test. Write the meaning of an edge as a comment before coding. - Boolean
visitedin directed DFS. Reaching an already-visited vertex is not a cycle unless that vertex is still on the stack. Use three colours (or a separateon_stackarray). - Forgetting isolated vertices. Vertices with no edges must still appear in the output. Build in-degrees for
0..n-1, not just for vertices mentioned in edges. In alien dictionary, letters that appear in no edge are still part of the alphabet. - Duplicate edges. Harmless if the in-degree and the adjacency list both count duplicates; wrong if one is a set and the other a multiset.
- Self-loops.
u → uis a cycle. Kahn handles it automatically (in-degree never reaches 0); a DFS that checks colour before marking also handles it. - Returning a partial order. Kahn's output on a cyclic graph looks like a normal list. Always compare its length with .
- Recursion depth. A path of vertices means nested calls. Use an explicit stack in Python (and increase the stack size or go iterative in C++/Java for ).
- Recomputing in-degrees per query. In-degrees are destroyed by the algorithm. If you need several sorts, copy the array.
- Expecting a unique answer. Unless the problem fixes a tie-break, many orders are correct. If a judge expects one, it will say "lexicographically smallest" or similar.
- Longest path with
bestinitialised to 0 when paths must start ats. Then unreachable vertices look reachable with weight 0. Initialise to and setbest[s] = 0. - Overflow in path counts. Counts double per diamond; take them modulo the given prime at every addition.
- Alien dictionary prefix case.
["abc", "ab"]is invalid. Also, only the first differing letter of each adjacent pair produces an edge. - Running DAG DP on a graph with cycles. It silently produces nonsense on the vertices Kahn did not output. Check for a cycle first, or condense SCCs.
Variations
- Kahn vs DFS. Same complexity. Kahn is iterative, naturally gives levels (rounds) and lexicographic order, and parallelizes (all ready vertices can be processed at once). DFS is convenient when you are already traversing, gives discovery/finish times, and is the basis for SCC algorithms (Connectivity).
- Reverse topological order (sinks first) comes for free from DFS postorder, and is what you need for "compute something from successors" DPs like transitive closure and "eventual safe states".
- Peeling on undirected graphs. Repeatedly removing degree-1 vertices from a tree finds its center(s) (Minimum Height Trees), and peeling vertices of degree gives the -core. Same queue mechanics, different degree notion.
- SCC condensation + topological sort. For graphs with cycles, collapse each strongly connected component into one vertex. The condensation is always a DAG, and you can run every algorithm in this lesson on it (used in 2-SAT, see 2-SAT & Coloring).
- Shortest paths in a DAG. The DAG DP with
minis single-source shortest paths in , negative edges allowed. Dijkstra and Bellman-Ford handle general graphs: Shortest Paths. - Dynamic (incremental) topological order. When edges arrive one at a time and you must keep an order (and reject cycle-creating edges), recomputing from scratch costs per edge. Pearce and Kelly ("A dynamic topological sort algorithm for directed acyclic graphs", ACM Journal of Experimental Algorithmics, 2006) reorder only the affected region between the edge's endpoints.
- Partial orders and linear extensions. In order-theory language, a DAG defines a partial order (via reachability) and a topological order is a linear extension. Counting them is #P-complete; sampling one uniformly at random is possible in polynomial time with Markov chain methods.
- DAG DP as general DP. Every memoized recursion with no cyclic dependencies is DP on the DAG of its states, processed in a topological order (which is what "bottom-up" means). Module 6, "DP on Graphs & DAGs", builds on exactly this view.
Practice ladder
Each problem is described in my own words; follow the link for the formal statement.
1. Course Schedule (LeetCode 207) — Decide whether a set of prerequisite pairs can all be satisfied. Teaches topological sort as cycle detection.
Hint
Kahn's algorithm, then compare the number of output vertices with . Remember that [a, b] means b → a.
2. Course Schedule II (LeetCode 210) — Same input; return one valid order or an empty list. Teaches returning the order and the partial-output trap.
Hint
Return Kahn's output if its length is , else [].
Solution
from collections import deque
def find_order(n: int, prerequisites: list[list[int]]) -> list[int]:
adj: list[list[int]] = [[] for _ in range(n)]
indeg = [0] * n
for course, pre in prerequisites:
adj[pre].append(course) # pre must come before course
indeg[course] += 1
q = deque(v for v in range(n) if indeg[v] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order if len(order) == n else []
assert find_order(3, [[1, 0], [2, 1]]) == [0, 1, 2]
assert find_order(2, [[0, 1], [1, 0]]) == []
assert sorted(find_order(3, [])) == [0, 1, 2]
print("course schedule II ok")
time and space for prerequisite pairs.
3. Course Schedule (CSES 1679) — Print any valid order of courses or report that none exists, with up to courses. Teaches fast iterative Kahn and 1-based input.
Hint
Identical algorithm; read all input at once in Python and avoid recursion.
4. Find All Possible Recipes from Given Supplies (LeetCode 2115) — Recipes need ingredients, some of which are other recipes; given initial supplies, list the makeable recipes. Teaches Kahn on a graph with string vertices and "initial sources" given by the input.
Hint
Edge from each ingredient to each recipe using it. Start the queue with the supplies. A recipe is makeable when its in-degree drops to 0. Recipes on cycles never do.
5. Find Eventual Safe States (LeetCode 802) — Find the vertices from which every walk ends at a terminal vertex. Teaches Kahn on the reversed graph (peeling sinks), or three-colour DFS.
Hint
Reverse every edge; terminal vertices now have in-degree 0. Peel them with Kahn; every vertex peeled is safe. Vertices on or leading into cycles are never peeled.
6. Minimum Height Trees (LeetCode 310) — Find the roots that minimise the height of a tree. Teaches peeling leaves level by level, Kahn's idea on an undirected graph.
Hint
Repeatedly remove all current leaves (degree 1). The last one or two vertices remaining are the centers. Handle separately.
7. Course Schedule IV (LeetCode 1462) — Answer many "is u a (direct or indirect) prerequisite of v?" queries. Teaches transitive closure.
Hint
: boolean Floyd-Warshall in , or bitsets filled in reverse topological order as in the variant above.
8. Longest Path (AtCoder Educational DP Contest G) — Length (in edges) of the longest directed path in a DAG with vertices. Teaches the DAG DP sweep.
Hint
dp[v] = max(dp[u] + 1) over edges u → v, in Kahn order. The answer is max(dp).
9. Longest Flight Route (CSES 1680) — Maximum number of cities on a route from city 1 to city in a DAG, and the route itself. Teaches longest path from a fixed source with initialisation and parent pointers.
Hint
Run the DP over all vertices in topological order, but only extend from vertices reachable from 1 (dp = -inf otherwise). Store parents; reconstruct from .
Solution
from collections import deque
def longest_flight_route(n: int, flights: list[tuple[int, int]]) -> list[int] | None:
adj: list[list[int]] = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for a, b in flights:
adj[a].append(b)
indeg[b] += 1
NEG = float("-inf")
dp = [NEG] * (n + 1) # max cities on a route 1 -> v
dp[1] = 1
parent = [0] * (n + 1)
q = deque(v for v in range(1, n + 1) if indeg[v] == 0)
while q:
u = q.popleft()
for v in adj[u]:
if dp[u] != NEG and dp[u] + 1 > dp[v]:
dp[v] = dp[u] + 1
parent[v] = u
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
if dp[n] == NEG:
return None # IMPOSSIBLE
route = [n]
while route[-1] != 1:
route.append(parent[route[-1]])
return route[::-1]
assert longest_flight_route(5, [(1, 2), (2, 5), (1, 3), (3, 4), (4, 5)]) == [1, 3, 4, 5]
assert longest_flight_route(3, [(2, 3)]) is None
assert longest_flight_route(4, [(2, 1), (1, 4), (2, 4)]) == [1, 4] # vertex 2 is not reachable from 1
print("longest flight route ok")
. The graph is guaranteed acyclic, so Kahn processes every vertex; vertices with in-degree 0 other than 1 simply propagate .
10. Game Routes (CSES 1681) — Count the routes from level 1 to level in a DAG, modulo . Teaches path counting.
Hint
ways[1] = 1; in topological order add ways[u] to every successor, mod .
Solution
from collections import deque
MOD = 10**9 + 7
def game_routes(n: int, edges: list[tuple[int, int]]) -> int:
adj: list[list[int]] = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for a, b in edges:
adj[a].append(b)
indeg[b] += 1
ways = [0] * (n + 1)
ways[1] = 1
q = deque(v for v in range(1, n + 1) if indeg[v] == 0)
while q:
u = q.popleft()
for v in adj[u]:
ways[v] = (ways[v] + ways[u]) % MOD
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return ways[n]
assert game_routes(4, [(1, 2), (2, 4), (1, 3), (3, 4), (1, 4)]) == 3
assert game_routes(3, [(2, 3)]) == 0
print("game routes ok")
.
11. Parallel Courses III (LeetCode 2050) — Courses have durations and prerequisites, any number can run at once; find the minimum total time. Teaches critical path.
Hint
Forward pass only: finish[v] = time[v] + max(finish[u]) over prerequisites u. The answer is max(finish).
Solution
from collections import deque
def minimum_time(n: int, relations: list[list[int]], time: list[int]) -> int:
adj: list[list[int]] = [[] for _ in range(n)]
indeg = [0] * n
for a, b in relations: # 1-based: a before b
adj[a - 1].append(b - 1)
indeg[b - 1] += 1
start = [0] * n # earliest start
q = deque(v for v in range(n) if indeg[v] == 0)
best = 0
while q:
u = q.popleft()
finish = start[u] + time[u]
best = max(best, finish)
for v in adj[u]:
start[v] = max(start[v], finish)
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return best
assert minimum_time(4, [[1, 2], [1, 3], [2, 4], [3, 4]], [1, 5, 2, 1]) == 7
assert minimum_time(3, [], [4, 1, 2]) == 4
print("parallel courses III ok")
. This is the ES/EF forward pass of CPM.
12. Largest Color Value in a Directed Graph (LeetCode 1857) — Each vertex has a colour (one of 26); find the path maximising the count of its most frequent colour, or report a cycle. Teaches DAG DP with a vector state plus cycle detection in one pass.
Hint
cnt[v][c] = max number of colour c on a path ending at v. Push cnt[u] into each successor in Kahn order, then add 1 for the vertex's own colour when it is popped. If Kahn does not output every vertex, return -1.
Solution
from collections import deque
def largest_path_value(colors: str, edges: list[list[int]]) -> int:
n = len(colors)
adj: list[list[int]] = [[] for _ in range(n)]
indeg = [0] * n
for u, v in edges:
adj[u].append(v)
indeg[v] += 1
cnt = [[0] * 26 for _ in range(n)]
q = deque(v for v in range(n) if indeg[v] == 0)
seen, best = 0, 0
while q:
u = q.popleft()
seen += 1
cnt[u][ord(colors[u]) - 97] += 1
best = max(best, cnt[u][ord(colors[u]) - 97])
for v in adj[u]:
cu, cv = cnt[u], cnt[v]
for c in range(26):
if cu[c] > cv[c]:
cv[c] = cu[c]
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return best if seen == n else -1
assert largest_path_value("aab", [[0, 1], [1, 2]]) == 2
assert largest_path_value("abab", [[0, 1], [0, 2], [2, 3], [1, 3]]) == 2
assert largest_path_value("a", [[0, 0]]) == -1
print("largest color value ok")
time, space.
13. Fox And Names (Codeforces 510C) — Given names that must appear sorted, find an ordering of the alphabet that makes it so, or say it is impossible. Teaches the alien-dictionary construction including the prefix case.
Hint
Edges from the first differing letter of each adjacent pair; if a name is followed by its own proper prefix, it is impossible. Include all 26 letters as vertices.
14. Course Schedule II (CSES 1757) — Find the valid order that places course 1 as early as possible, then course 2, and so on. Teaches why lexicographic-smallest is the wrong greedy and the reversed max-heap fix.
Hint
Reverse every edge, run Kahn with a max-heap, reverse the output. See "Lexicographically smallest order" above for the three-vertex counterexample.
15. Sort Items by Groups Respecting Dependencies (LeetCode 1203) — Items belong to groups; items of a group must be contiguous and item dependencies must be respected. Teaches two-level topological sort.
Hint
Give ungrouped items their own fresh group. Topologically sort the groups (edges from cross-group dependencies) and, separately, the items (all dependencies). Then emit groups in group order, each group's items in item order. Either sort failing means no answer.
Common mistakes & interview follow-ups
"Is the topological order unique?" It is unique iff Kahn's queue never holds more than one vertex, which happens iff the order's consecutive vertices are all joined by edges, i.e. the DAG has a Hamiltonian path. You can check it during Kahn in .
"How do you print the cycle, not just detect it?" In DFS, when you meet a gray vertex from , walk the parent pointers from up to . In Kahn, take any unoutput vertex and walk backwards along edges from other unoutput vertices until a vertex repeats.
"What if the graph does not fit in memory?" Kahn's working state is small: the in-degree array ( bytes) and the queue. What it needs from the edges is each popped vertex's out-list, so store edges sorted by source (a CSR file on disk) and read one vertex's out-edges at a time; the reads are random, which is the expensive part. External-memory topological sorting is a research topic in its own right; in practice large systems partition the graph so each part fits in memory.
"How do you run it in parallel?" Process Kahn level by level: every vertex in the current level is independent, so all can run at once. The number of levels is the longest path length, which bounds the parallel time — the same reasoning as make -j and graphlib.TopologicalSorter.
"Edges arrive over time; keep the order up to date." Incremental topological ordering (Pearce-Kelly): when a new edge goes backwards in the current order, reorder only vertices whose positions lie between and ; reject the edge if reaches .
"Longest path in a general graph?" NP-hard (Hamiltonian path reduces to it). Only acyclic graphs, or graphs with special structure, are easy. If cycles exist but weights make cycles unattractive, you are really solving shortest paths with negated weights, which needs Bellman-Ford.
"Why not just sort by depth from a source?" BFS depth is not a topological order: with edges A → B, B → C, A → C, BFS from A gives C depth 1 and B depth 1, so a depth-sorted order may put C before B. Longest-path depth would work, and that is exactly Kahn's level.
Common mistakes interviewers watch for: reversed edges; boolean visited for directed cycle detection; not checking len(order) == n; recursion on deep graphs; missing isolated vertices; forgetting the alien-dictionary prefix case.
Quick quiz
1. Kahn's algorithm on a 10-vertex graph outputs 6 vertices and stops. What can you say about the other 4?
Answer
Each of them lies on a directed cycle or is reachable from one; the graph is not a DAG. At least 2 of them (a cycle needs at least 2 vertices, or 1 with a self-loop) form a cycle.
2. Why is "reverse postorder" a topological order but "preorder" (discovery order) is not?
Answer
For every edge in a DAG, finishes before (Theorem 3), so decreasing finish time puts first. Discovery times have no such guarantee: with roots tried in order C, A and edges A → C, C is discovered first.
3. In the example DAG, what does Kahn output with a min-heap, and why does it differ from the FIFO version?
Answer
A B F C D G E. After popping A, the ready set is {F, B}. FIFO takes F because it was enqueued first; the heap takes B because it is smaller.
4. In the PERT example, the UI task D takes 9 days instead of 4. What is the new project length and critical path?
Answer
D finishes at , so F starts at and finishes at 14; H finishes at 15. New length 15 days, critical path A → D → F → H ().
5. Why does single-source shortest paths in a DAG work with negative edges in , while Dijkstra does not?
Answer
The topological order guarantees that when a vertex is processed, all its incoming edges have been relaxed, regardless of weights. Dijkstra's order is by tentative distance, which is only safe when no later edge can lower a finalized distance, i.e. when weights are non-negative.
Further reading / sources
- Arthur B. Kahn, "Topological sorting of large networks", Communications of the ACM 5(11):558–562, 1962.
- Robert E. Tarjan, "Edge-disjoint spanning trees and depth-first search", Acta Informatica 6:171–185, 1976 (DFS-based topological sorting).
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed.: section 22.3 (DFS, white-path theorem), 22.4 (topological sort), 24.2 (single-source shortest paths in DAGs).
- Sedgewick and Wayne, Algorithms, 4th ed., section 4.2 "Directed Graphs" (topological sort, cycle detection, precedence-constrained scheduling).
- Steven Skiena, The Algorithm Design Manual, 3rd ed., the graph-traversal chapter (DFS applications on directed graphs) and the catalog entry "Topological Sorting".
- Antti Laaksonen, Competitive Programmer's Handbook, chapter 16 "Directed graphs" (topological sorting, DP on DAGs, successor paths).
- cp-algorithms: Topological Sorting and Checking a graph for acyclicity and finding a cycle.
- Graham Brightwell and Peter Winkler, "Counting linear extensions", Order 8:225–242, 1991.
- J. D. Ullman, "NP-complete scheduling problems", Journal of Computer and System Sciences 10(3), 1975; E. G. Coffman and R. L. Graham, "Optimal scheduling for two-processor systems", Acta Informatica 1, 1972.
- David J. Pearce and Paul H. J. Kelly, "A dynamic topological sort algorithm for directed acyclic graphs", ACM Journal of Experimental Algorithmics 11, 2006.
- Python documentation:
graphlib— functionality to operate with graph-like structures. - GNU Make manual, chapter "Writing Rules" and section "Parallel Execution".
Previous lesson: DFS in Depth · Next lesson: Shortest Paths
Related: Graphs overview · BFS in Depth · Graph Modeling & Implicit Graphs · Connectivity & SCCs · Queues & Deques · Heaps & Priority Queues · Dynamic Programming · OS Algorithms · Course home