Topological Sort on Complementary DAG

Правка en1, от code_warrior, 2021-02-02 08:31:08

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.

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский code_warrior 2021-02-02 08:33:10 79
en1 Английский code_warrior 2021-02-02 08:31:08 825 Initial revision (published)