Why is my logic not working correctly for SPOJ TOPOSORT?

Question

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 function ) 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.

Answer 1

I think the issue here is that the DFS topological sorting algorithm is only guaranteed to produce a valid topological sort, not the lexicographically first topological sort (which is what you need).

One way you could potentially fix this is to change which algorithm you're using to perform a topological sort. Rather than using DFS, consider using the other standard algorithm, which works by maintaining a set of all nodes with indegree 0, then repeatedly removing one and updating the set of nodes with indegree 0. If you use a priority queue to choose the node with indegree 0 and with lowest numerical value on each iteration, you'll get back a topological sort that satisfies the constraints given by the problem.

Hope this helps!