Sorting post numbers in a graph in $O(n)$ time After running dfs on a graph, we get a list of n post and pre numbers. How do we sort this list in $O(n)$ time instead of $O(n\log n)$ time?
You cheat. At the moment where you assign the post number, you know that it's the greatest post number so far. So you just keep a list vertices and whenever a vertex gets assigned a post number, you push it at the head of the list. At the end, the list will contain all vertices in decreasing post order. If you want them in increasing post order, you just have to reverse it which is $O(n)$. The same thing works for pre numbers.