v. DAGs and Topological Sort

A directed graph has a topological order iff it is acyclic. Kahn’s algorithm (repeatedly remove an in-degree-0 vertex) and DFS finishing order both find one in $O(n+m)$ and both detect cycles. In topological order every DAG DP is one loop: shortest/longest paths with any weights, path counts, reachability (DAG DP). For graphs with cycles, condense SCCs first (SCC).

vector<int> kahn(const vector<vector<int>>& g) {           // empty if there is a cycle
    int n = sz(g); vector<int> in(n), ord;
    for (auto& e : g) for (int v : e) in[v]++;
    for (int v = 0; v < n; v++) if (!in[v]) ord.push_back(v);
    for (int i = 0; i < sz(ord); i++) for (int v : g[ord[i]]) if (!--in[v]) ord.push_back(v);
    return sz(ord) == n ? ord : vector<int>{};
}

DFS version: append each vertex when it finishes, then reverse. Prefer Kahn when recursion depth is a concern (it’s iterative by construction) or when you need the lexicographically-smallest order via a heap; prefer the DFS version when the topological order is only a preprocessing step inside a larger DFS-based algorithm (e.g. 2-SAT, which assigns truth values in reverse topological order of the implication graph’s condensation).

Proof: Kahn and the DFS order are topological orders, and cycles are detected

Kahn: a vertex is appended only after all its in-edges were removed, i.e. after all its predecessors were appended. If the graph is a DAG, every nonempty remaining subgraph has a source (otherwise walking backwards forever would repeat a vertex: a cycle), so the process never gets stuck. If there is a cycle, no vertex on it can reach in-degree 0 before another vertex on it is removed, so none is ever removed and fewer than $n$ vertices are output.
DFS: for an edge $u\to v$ in a DAG, when $u$ scans it, $v$ is either white (then $v$ finishes inside $u$‘s call, before $u$) or black (already finished); it can’t be grey, since a grey $v$ is an ancestor of $u$ and the edge would close a cycle. So $v$ finishes before $u$, and reversing finishing order puts $u$ first.

Variants

Need	How
lexicographically smallest order	Kahn with a min-heap
vertex 1 as early as possible, then 2, then 3, … (not lexicographic!)	Kahn on the reversed graph with a max-heap, then reverse the output
is the order unique?	Kahn’s queue never holds two vertices at once ⟺ there is a Hamiltonian path
count topological orders	bitmask DP $O(2^{n}n)$; for a forest (tree poset) $n!/{\prod }_v\text{size}(v)$
layers / longest chain	${\text{lvl}}_v=1+\max {\text{lvl}}_{\text{pred}}$ (Mirsky: min antichain cover = longest chain)
min number of chains covering (paths may share vertices)	Dilworth: transitive closure + bipartite matching
parallel scheduling with $k$ machines and unit jobs	NP-hard for general $k$; $k=2$ is polynomial (Coffman–Graham); trees: Hu’s level algorithm
longest simple path	linear time via the DAG DP above — note this is specifically what acyclicity buys you, since longest simple path is NP-hard on general graphs

Proof: the reversed max-heap trick and the tree formula

Reversed max-heap: compare orders by $(\text{pos}(1),\text{pos}(2),\dots )$ lexicographically. Let $b$ be the largest sink. Take any valid order $\pi$ not ending with $b$, and move $b$ to the end; this stays valid because $b$ has no successors. Vertices that were after $b$ move one step earlier, $b$ moves later, nothing else changes. The last vertex of $\pi$ is a sink $s\ne b$, so $s<b$ and $s$ was after $b$: the smallest label whose position changed is $<b$ and it moved earlier, so the new order is strictly better. Hence every optimal order ends with $b$; remove $b$ and repeat on the rest. That is exactly Kahn on the reversed graph with a max-heap, output reversed.
Trees: for a rooted forest where each vertex must come after its parent, a uniformly random permutation is valid iff every vertex is the first of its subtree, events that are independent across vertices with probabilities $1/\text{size}(v)$. So the count is $n!/{\prod }_v\text{size}(v)$.
Mirsky: label $v$ by the number of vertices on the longest chain ending at $v$. Two comparable vertices get different labels, so each label class is an antichain, and the number of classes is the longest chain; fewer antichains can’t work since a chain meets each antichain at most once.

Reachability

Transitive closure with bitsets: in reverse topological order, ${\text{reach}}_u=\{u\}\cup {\bigcup }_{u\to v}{\text{reach}}_v$. $O(nm/64)$ time and $n^2/8$ bytes ($n=5\cdot 10^4$ is about 312 MB; process 64 targets at a time with one word per vertex when memory is tight).

vector<vector<ull>> closure(const vector<vector<int>>& g, const vector<int>& topo) {   // g a DAG
    int n = sz(g), W = (n + 63) / 64; vector<vector<ull>> r(n, vector<ull>(W));
    for (int i = n - 1; i >= 0; i--) {
        int u = topo[i]; r[u][u >> 6] |= 1ULL << (u & 63);
        for (int v : g[u]) for (int w = 0; w < W; w++) r[u][w] |= r[v][w];
    }
    return r;
}

Incremental reachability (insert edges into a DAG, reject edges creating a cycle, $O(1)$ queries) in $O(n)$ amortised per insertion, $O(n^2)$ memory: for every source $p$ keep a spanning tree of the vertices reachable from $p$; inserting $u\to v$ grafts the part of $v$‘s tree that $p$ doesn’t reach yet into the tree of every $p$ that reaches $u$ (Italiano).

struct IncReach {
    int n; vector<vector<int>> par; vector<vector<vector<int>>> ch;   // par[p][v]: parent of v in p's tree, -1 unreachable
    IncReach(int n) : n(n), par(n, vector<int>(n, -1)), ch(n, vector<vector<int>>(n)) {}
    bool reach(int s, int t) const { return s == t || par[s][t] >= 0; }
    bool addEdge(int s, int t) {
        if (reach(t, s)) return false;                      // would close a cycle
        if (reach(s, t)) return true;
        for (int p = 0; p < n; p++) if (reach(p, s) && !reach(p, t)) meld(p, t, s, t);
        return true;
    }
    void meld(int root, int sub, int u, int v) {
        par[root][v] = u; ch[root][u].push_back(v);
        for (int c : ch[sub][v]) if (!reach(root, c)) meld(root, sub, v, c);
    }
};

Proof: Italiano's grafting is $O(n^3)$ in total

Correctness: after inserting $u\to v$, the vertices newly reachable from $p$ are exactly those reachable from $v$ but not yet from $p$; walking $v$‘s own reachability tree and stopping at vertices $p$ already reaches visits exactly them (if $p$ already reaches $c$, it already reaches everything $c$ reaches). Cost: every step of meld(root, ...) makes a new pair $(\text{root},c)$ reachable, and each of the $n^2$ pairs becomes reachable once; scanning children of $c$ in sub’s tree is charged to the newly reachable $c$, and a vertex has at most $n$ children per tree, so the grafting work is $O(n^3)$ over any sequence of insertions, plus $O(n)$ per insertion for the loop over $p$.

For general static reachability queries on large sparse graphs there is no near-linear exact method; options are bitsets ($n\le 5\cdot 10^4$), offline processing in blocks of 64 targets, or exploiting structure (planar/trees: interval labels; DAGs from DP: problem-specific).