Why is my logic not working correctly for SPOJ TOPOSORT?

Posted by Kavish Dwivedi on Stack Overflow See other posts from Stack Overflow or by Kavish Dwivedi
Published on 2013-06-26T11:17:40Z Indexed on 2013/07/01 17:08 UTC
Read the original article Hit count: 398

Filed under:
|

The given problem is http://www.spoj.com/problems/TOPOSORT/ The output format is particularly important as :

Print "Sandro fails." if Sandro cannot complete all his duties on the list. 
If there is a solution print the correct ordering, 
the jobs to be done separated by a whitespace. 
If there are multiple solutions print the one, whose first number is smallest, 
if there are still multiple solutions, print the one whose second number is smallest, and so on. 

What I am doing is simply doing dfs by reversing the edges i.e if job A finishes before job B, there is a directed edge from B to A . I am maintaining the order by sorting the adjacency list I created and storing the nodes which don't have any constraints separately so as to print them later in correct order . There are two flag arrays used , one for marking discovered node and one for marking the node whose all neighbors have been explored.

Now my solution is http://www.ideone.com/QCUmKY (the important function is the visit funtion ) and its giving WA after running correct for 10 cases so its really hard to figure out where am I doing it wrong since it runs for all of the test cases which I have done by hand.

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about spoj