 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$. ThereforeEach 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.