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!

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 cause is that you visit the vertices in the index order; however, a higher order index could lead to a low index node.

There should be a simple O(m + nlogn) solution to this problem, but I cannot see how to fix your code easily. You know this code the best since you wrote, so good luck fixing it.

Answer 3

The dfs algorithm times out in this particular question. With some clever tricks you can get the complexity of the solution to O(m). You need to eliminate the sort that you are using to sort all the edges in order. I maintained a list of reverse edges, i.e for two edges u->v and w->v, I initially added them in the list li[v]->u->w. and then traversing from 1 to n, I created the corrected directed edges, but this time they come out to be automatically in order.

Anyway this times out(on test case12 for me). You need a very optimized algorithm for this. The algorithm templatetypedef mentions works fine, probably the recursion overhead in dfs is a bit too much in the dfs algorithm.

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

Basically, you can complete the tasks with zero indegree and once the task is completed, you remove all the outgoing edges and update all the indegrees and find another task with zero indegree. To get things in order, you can use a 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;
}