Topological Sort in C++: Kahn's Algorithm and Longest Path DAG
Kahn's algorithm in C++ for contests: in-degrees, a queue or min-heap for the smallest order, cycle detection by count, and DP over a DAG for longest paths.
- Course: Competitive Programming study plan
- Module: Topological sort and DAGs
- Kind: Lesson
- Reading time: 14 min
- Runtime: Clang 18 · C++20
What is Kahn's algorithm for topological sort?
Kahn's algorithm orders the vertices of a directed acyclic graph (DAG) so every edge points forwards. It counts each vertex's in-degree, queues every vertex with in-degree 0, and repeatedly removes one, appends it to the order and lowers its neighbours' in-degrees, queueing any that reach 0. It runs in O(V + E); fewer than V vertices placed means the graph has a cycle.
Lesson
A topological order lists a DAG's vertices so every edge a → b has a before b — prerequisites before courses, tasks before what depends on them. It exists exactly when there is no cycle.
Kahn's algorithm
- Count
indeg[v], the number of edges intov. - Every vertex with
indeg == 0is ready: nothing has to come before it. - Take a ready vertex, append it, and cross off its out-edges; a neighbour that drops to 0 becomes ready.
- Ready set a
queue→ any valid order. A min-heap → the lexicographically smallest one.
priority_queue<int, vector<int>, greater<>> ready;
for (int v = 1; v <= n; ++v) if (indeg[v] == 0) ready.push(v);
vector<int> order;
while (!ready.empty()) {
int u = ready.top(); ready.pop();
order.push_back(u);
for (int v : adj[u]) if (--indeg[v] == 0) ready.push(v);
}
bool cycle = (int)order.size() < n;edges = 3→1, 3→4, 2→4, 4→6, 1→6, 6→5, 1→5- Count the arrows into each course: 1 has 1, 2 has 0, 3 has 0, 4 has 2, 5 has 2, 6 has 2. Courses 2 and 3 need nothing first, so they start in the ready min-heap.
- Pop 2, the smallest ready course, and append it to the order. The heap hands out the smallest ready course, which makes the order the lexicographically smallest one. Cross off its arrows: 4 drops to 1.
- Pop 3, the smallest ready course, and append it to the order. Cross off its arrows: 1 drops to 0, 4 drops to 0. 1 and 4 reach 0 and join the heap.
- Pop 1, the smallest ready course, and append it to the order. Cross off its arrows: 6 drops to 1, 5 drops to 1.
- Pop 4, the smallest ready course, and append it to the order. Cross off its arrows: 6 drops to 0. 6 reaches 0 and joins the heap.
- Pop 6, the smallest ready course, and append it to the order. Cross off its arrows: 5 drops to 0. 5 reaches 0 and joins the heap.
- Pop 5, the smallest ready course, and append it to the order. It has no arrows out.
- The heap is empty and all 6 courses are placed: 2, 3, 1, 4, 6, 5. Every arrow points forwards in it. Had fewer than 6 been placed, the rest would sit on a cycle.
Cycles
- On a cycle every vertex waits for another of the cycle, so none reaches 0.
order.size() < nis the cycle test — no separate DFS needed.
DP on a DAG
The order is a schedule for dynamic programming: when u comes up, every path into it is already counted.
- Longest path:
best[v] = max(best[v], best[u] + w)over edges in order — O(V + E), though NP-hard on general graphs. - Number of paths
1 → n:ways[v] += ways[u], mod 10^9 + 7. - Fewest semesters (any number of courses at once):
level[v] = max(level[v], level[u] + 1).
Pitfalls
- A queue where the statement wants the smallest order — use the min-heap.
- Recursing in a DFS topo sort on a 10^5-vertex chain: stack overflow. Kahn's is iterative.
- Longest path with
int: 10^5 edges of 10^9 needslong long.
More practice
Common questions
How do you get the lexicographically smallest topological order?
Run Kahn's algorithm with a min-heap — priority_queue<int, vector<int>, greater<>> — instead of a queue, so the smallest ready vertex is always taken next. It costs O((V + E) log V).
How does Kahn's algorithm detect a cycle?
Vertices on a cycle each wait for another vertex of the cycle, so none of them ever reaches in-degree 0. If the order ends with fewer than V vertices, the leftovers lie on a cycle or behind one, and no topological order exists.
How do you find the longest path in a DAG?
Process the vertices in topological order and relax each edge u → v with best[v] = max(best[v], best[u] + w). Every path into u is final before u is processed, so one pass gives the answer in O(V + E), even though longest path is NP-hard on general graphs.
What is the difference between Kahn's algorithm and DFS topological sort?
Both run in O(V + E). Kahn's peels in-degree-0 vertices with a queue and detects a cycle by count; the DFS version outputs vertices in reverse post-order and detects a cycle by meeting a vertex still on the recursion stack. Kahn's has no recursion depth to worry about.
Exercises
The smallest course order
There are n courses 1 to n and m rules a b, each meaning course a must be taken before course b. Print an order that takes every course after all of its prerequisites; among all such orders, print the lexicographically smallest (compare the first course, then the second, …). Print IMPOSSIBLE if no order exists.
Input: n m, then m lines a b (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 2·10^5, a ≠ b). Output: the n courses on one line separated by spaces, or IMPOSSIBLE.
6 7
3 1
3 4
2 4
4 6
1 6
6 5
1 5prints
2 3 1 4 6 5The longest path in a DAG
A directed acyclic graph has vertices 1 to n and m weighted edges. Print the largest total weight of any path (a path may start and end anywhere; a single vertex is a path of weight 0).
Input: n m, then m lines u v w (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 2·10^5, 1 ≤ w ≤ 10^9). The graph has no cycle. Output: one integer.
5 6
1 2 3
1 3 2
2 4 4
3 4 6
4 5 1
2 5 2prints
9The path 1 → 3 → 4 → 5 weighs 2 + 6 + 1.
In this module: Topological sort and DAGs
← Checkpoint — Shortest paths · Checkpoint — Topological sort and DAGs →