Chapter 3 · Directed Graphs
DAGs and Topological Order
Two algorithms, one equivalence, and DP on a DAG as the default solution shape.
A directed acyclic graph is a digraph with no directed cycle. A topological order is a permutation v1, …, vn such that every edge vi → vj has i < j.
G has a topological order ⇔ G is a DAG.
(⇐) A non-empty DAG has a vertex of indegree 0 (otherwise walk backwards forever and repeat a vertex → cycle). Put it first and induct. (⇒) An order is a strict ranking: along any directed walk indices strictly increase, so no vertex can repeat — there are no cycles. ∎
#Kahn's algorithm (queue of zero-indegree)
vector<int> indeg(n);
for (auto [u, v] : edges) indeg[v]++;
queue<int> q;
for (int i = 0; i < n; i++) if (!indeg[i]) q.push(i);
vector<int> order;
while (!q.empty()) {
int u = q.front(); q.pop();
order.push_back(u);
for (int v : g[u]) if (!--indeg[v]) q.push(v);
}
if (order.size() != n) return {}; // cycle: the leftovers contain oneVertices remaining after Kahn have positive indegree inside the leftover set; walking backwards through them must repeat a vertex, which yields a directed cycle. So "cycle detection", "topological sort" and "find one cycle" are the same 10 lines. Use priority_queue instead of queue if you need the lexicographically smallest order — same complexity plus a log.
#DFS post-order version
vector<int> col(n), order;
bool cyc = false;
function<void(int)> dfs = [&](int u) {
col[u] = 1; // grey: on the stack
for (int v : g[u]) {
if (col[v] == 1) cyc = true; // back edge
else if (!col[v]) dfs(v);
}
col[u] = 2;
order.push_back(u);
};
for (int i = 0; i < n; i++) if (!col[i]) dfs(i);
reverse(order.begin(), order.end()); // topological orderBoth are O(n+m); DFS needs a stack (or std::function overhead), Kahn needs the indegree array. Prefer Kahn in contests — no recursion depth risk, and the "leftovers = cycle" check is one line.
#The real prize: DP on a DAG
Once vertices are ordered, every "longest path / number of paths / reachable set" question is a single sweep: process u, push your value into each successor.
// number of paths s -> v, and longest path length, in one pass
vector<long long> ways(n); vector<int> best(n, -INF);
ways[s] = 1; best[s] = 0;
for (int u : order) {
for (int v : g[u]) {
ways[v] += ways[u]; // mod M if asked
best[v] = max(best[v], best[u] + w(u, v));
}
}"Each task takes 1 unit / requires other tasks / can be done in some order…" plus n up to 2 × 105 = toposort. If the graph has cycles, ask whether you should condense it (Strongly Connected Components) first: a cycle inside a "must-be-ordered" model usually means "these are equivalent", not "impossible".
Four problems that are one DAG sweep
- Longest path in a DAG: the
bestline above; NP-hard on general graphs (Held–Karp: Hamilton in O(2ⁿn²)). - Counting paths mod M: the
waysline (CSES Game Routes, 1681). - Reachability bitsets:
reach[u] |= reach[v], O(nm/64) (CSES 2138 Reachable Nodes). - Minimum path cover: after toposort, build the bipartite graph and run matching (Matching Applications, Dilworth).
Kahn's algorithm with the indegree array exposed. Flip to 'with a cycle' to see the leftovers and the failed output.