Topological Sort on Complementary DAG

Revision en2, by code_warrior, 2021-02-02 08:33:10

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English code_warrior 2021-02-02 08:33:10 79
en1 English code_warrior 2021-02-02 08:31:08 825 Initial revision (published)