---
title: "DAGs and Topological Order"
summary: Two algorithms, one equivalence, and DP on a DAG as the default solution shape.
difficulty: core
tags: [DAG, ordering, DP]
time: n + m
space: n
prereq: [directed/definitions, trees/dfs]
see: [directed/cycles, directed/scc, shortest/sparse-tricks]
---

:::definition label="DAG"
A **directed acyclic graph** is a digraph with no directed cycle. A **topological order** is a permutation $v_1, \dots, v_n$ such that every edge $v_i \to v_j$ has $i < j$.
:::

:::theorem title="The fundamental equivalence"
$G$ has a topological order $\iff$ $G$ is a DAG.
:::

:::proof
$(\Leftarrow)$ A non-empty DAG has a vertex of indegree 0 (otherwise walk backwards forever and repeat a vertex → cycle). Put it first and induct.
$(\Rightarrow)$ 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)
```cpp kahn.cpp
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 one
```

:::note title="Why the leftover is a cycle, not just a mess"
Vertices 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
```cpp toposort-dfs.cpp
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 order
```
Both 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.

```cpp dag-dp.cpp
// 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));
    }
}
```

:::idea title="Recognition pattern"
"Each task takes 1 unit / requires other tasks / can be done in some order…" plus $n$ up to $2 \times 10^5$ = toposort. If the graph has cycles, ask whether you should **condense it** (@directed/scc) first: a cycle inside a "must-be-ordered" model usually means "these are equivalent", not "impossible".
:::

:::props title="Four problems that are one DAG sweep"
- **Longest path in a DAG**: the `best` line above; NP-hard on general graphs (@euler/hamilton-dp).
- **Counting paths** mod $M$: the `ways` line (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).
:::

:::demo id="toposort" caption="Kahn's algorithm with the indegree array exposed. Flip to 'with a cycle' to see the leftovers and the failed output."
:::

:::problems
- [[CSES 1679]] Course Schedule | https://cses.fi/problemset/task/1679 | easy | Kahn
- [[CSES 1681]] Game Routes | https://cses.fi/problemset/task/1681 | core | DAG counting
- [[CSES 1680]] Longest Flight Route | https://cses.fi/problemset/task/1680 | core | DAG DP
- [[CF 1385E]] Directing Edges | https://codeforces.com/problemset/problem/1385/E | core | mixed graph
:::