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
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