Why is my logic not working correctly for SPOJ TOPOSORT?

Question

This issue is http://www.spoj.com/problems/TOPOSORT/ The output format is especially 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 just doing dfs, reversing the edges ie if task A ends before task B, there is a directed edge from B to A. I maintain order by sorting the adjacency list that I created and keep nodes that don't have any - or restrictions separately, to print them later in the correct order. Two used flag arrays are used: one for marking detected nodes and one for marking nodes whose neighbors have been studied.

Now my solution is http://www.ideone.com/QCUmKY (the important function is the visit function) and its providing WA after working correctly in 10 cases, so it’s really hard to understand where I am doing it wrong, since it works for everyone test cases that I did manually.

Answer 1

I think the problem here is that the DFS topological sorting algorithm is only guaranteed to get a real topological sort, and not for the lexicographically first topological sort (which is what you need).

One of the ways you can fix this is to change the algorithm that you use to perform topological sorting. Instead of using DFS, consider using another standard algorithm that works by maintaining a set of all nodes with an undefined value of 0, then repeatedly deleting one and updating a set of nodes with an undefined value of 0. If you use the priority queue to select a node with index 0 and the lowest numerical value at each iteration, you will return a topological view that satisfies the constraints posed by the problem.

Hope this helps!

Answer 2

Here is one input that breaks your program:

 4 4 2 4 4 1 3 1 

The answer should be 2 3 4 1, but your code prints 3 2 4 1.

The reason is that you visit the vertices in index order; however, a higher order index may result in a lower node index.

There must be a simple O (m + nlogn) solution to solve this problem, but I cannot figure out how easy it is to fix your code. You know that this code is the best since you wrote, so good luck with this fix.

Answer 3

The dfs algorithm is played out in this particular question. With some clever tricks, you can get the complexity of solving O (m). You need to eliminate the sorting you use to sort all the edges in order. I saved a list of back edges, i.e. For two edges u-> v and w-> v, I initially added them to the list li [v] → u-> w. and then, going from 1 to n, I created fixed directed edges, but this time they come out automatically in order.

In any case, this is the time (in test case 12 for me). For this you need a very optimized algorithm. The templatetypedef algorithm mentions that it works fine, perhaps the recursion overhead in dfs is too much in the dfs algorithm.

The idea is very simple, you can read about it here http://en.wikipedia.org/wiki/Topological_sorting

In principle, you can perform tasks with a zero index, and after the task is completed, you delete all outgoing edges and update all indexes and find another task with a zero index. To keep everything in order, you can use the priority queue.

  #include <iostream>
 #include <vector>
 #include <queue>

 using namespace std;
 int indeg [10005];
 int topo [10005];
 vector <int> g [10005];
 int main () {
         int n, m;
         int cur = 0;
         cin >> n >> m;
         for (int i = 0; i <m; i ++) {
                 int x, y;
                 scanf ("% d% d", & x, & y);
                 indeg [y] ++;
                 g [x] .push_back (y);
         }
         priority_queue <int> q;
         for (int i = 1; i <= n; i ++)
                 if (! indeg [i]) q.push (-1 * i);
         while (! q.empty ()) {
                 int nd = -1 * q.top ();
                 q.pop ();
                 for (int i = 0; i <g [nd] .size (); i ++) {
                         indeg [g [nd] [i]] -;
                         if (! indeg [g [nd] [i]])
                                 q.push (-1 * g [nd] [i]);
                 }
                 topo [cur ++] = nd;
         }
         if (cur! = n) {
                 cout << "Sandro fails."  << endl;
                 return 0;
         }

         for (int i = 0; i <n-1; i ++)
                 printf ("% d", topo [i]);
         printf ("% d \ n", topo [n-1]);


         return 0;
 }