Topological sort
An order of the vertices of a DAG in which every edge points forward, in . Every DP on a DAG runs on top of it.
When
Dependencies ("course before "), or a DP on a directed acyclic graph: longest path, number of paths, anything computed from the predecessors.
The idea (Kahn)
A vertex with no incoming edges can go first. Place it, delete its edges, and some other vertices are left with no incoming edges. Keep the in-degree of every vertex and a queue of those with in-degree 0.
If at the end fewer than vertices have come out, the rest always have some incoming edge among themselves. So there is a cycle, and the function returns an empty vector.
DP on a DAG
In Longest Flight Route you compute the longest path from to . Go through the vertices in topological order, so that when you reach all its predecessors are done:
Game Routes is the same with a sum instead of a maximum, modulo .
Pitfalls
- A topological order is not unique. If the problem wants the lexicographically smallest one, replace the queue with a
priority_queue(smallest first). - In
Longest Flight Route, vertices not reachable from must not contribute. Start with everywhere except .
Code
No main: it goes below the #include lines, using namespace std and using ll = long long.
// Topological order of a directed graph (Kahn's algorithm). O(n + m).
// Returns an empty vector if the graph has a cycle.
vector<int> topologicalSort(const vector<vector<int>>& adj) {
int n = adj.size();
vector<int> indeg(n, 0);
for (int u = 0; u < n; u++) {
for (int v : adj[u]) {
indeg[v]++;
}
}
queue<int> q;
for (int u = 0; u < n; u++) {
if (indeg[u] == 0) {
q.push(u);
}
}
vector<int> order;
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : adj[u]) {
indeg[v]--;
if (indeg[v] == 0) {
q.push(v);
}
}
}
if ((int)order.size() < n) {
return {};
}
return order;
}
Tested on 2,000 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
Practice on CSES
In order: the first is the plain application, the rest need a twist.
- Course Schedule · Graph Algorithms
- Longest Flight Route · Graph Algorithms
- Game Routes · Graph Algorithms
More in the USACO Guide
- Topological Sort · usaco.guide/gold/toposort
In English, with more problems per level.