Extend reachability to total ordering Given a finite DAG $G = (V, E)$ with $|E| \in \mathcal{O}(|V|)$, I want to compute a total ordering $&lt;$ over $V$ that is compatible to reachability: If there is a transition $(u, v) \in E$, then $u &lt; v$.

The only way I could think of was to use Floyd-Warshall to compute a reachability matrix and then somehow extend that to be total. This would require cubic time, which is too slow for my needs. I require a quadratic time algorithm at most. In a publication I read that this is actually possible in linear time but no procedure or further explanation was provided.
You can compute a topological ordering of the vertices in linear time.