= Solution
Use <Kahn's algorithm> for <topological sorting>. With an <adjacency list> representation, count every <vertex>'s <indegree> by scanning the <edges>. Put all zero-<indegree> <vertices> in a <queue>. Repeatedly remove one such <vertex> $u$, append it to the output, and delete its outgoing <edges> by decrementing the stored <indegree> of each neighbour; enqueue a neighbour exactly when its count becomes zero.
The <loop invariant> is that stored counts are the <indegrees> in the unreported subgraph and the <queue> contains exactly its unreported zero-<indegree> <vertices>. A nonempty finite <Directed acyclic graph> always has such a <vertex>: otherwise following incoming <edges> would eventually repeat a <vertex>, creating a directed <graph cycle>. Thus the <queue> cannot become empty while any <vertex> remains.
For every original <edge> $u\to v$, $v$ cannot enter the output until that <edge> has been removed by outputting $u$. Therefore
$$
\boxed{u\to v\implies\operatorname{position}(u)<\operatorname{position}(v).}
$$
Each <vertex> enters and leaves the <queue> once, and every <edge> is scanned a constant number of times, giving $\boxed{\Theta(|V|+|E|)}$ time and $O(|V|)$ auxiliary space beyond the <adjacency lists>. If given only an <adjacency matrix>, scanning neighbours instead takes $\Theta(|V|^2)$ time.
Back to article page
