Блог пользователя code_warrior

Автор code_warrior, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

check this