code_warrior's blog

By code_warrior, history, 3 years ago, In English

Hello, friends. Recently, I was solving this problemTopological Sort, but got stuck on it. I thought a lot for solving but couldn't come up with any efficient approach. There is even no tutorial available for it. My Approach (May or must be wrong, that's why i am getting wrong answer)-: For every node I am finding the first node greater than it to which it will be connected and also the largest node smaller than it which will connect to it. After forming a DAG in this way with no more than 2*n edges I ran toposort on it. But it's giving me wrong answer. See the drawing for understanding my approach. This one

Can someone help me figuring out the way to solve this problem? I bet this is one of the most nice problems on graph theory.

  • Vote: I like it
  • +18
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

check this