0

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?

xavierm02
  • 1,255
  • 6
  • 14
matt
  • 147
  • 3
  • Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. – Raphael Apr 07 '17 at 19:27

1 Answers1

2

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.

xavierm02
  • 1,255
  • 6
  • 14