This is a problem in a past contest and its link is:

http://codeforces.com/gym/101102/problem/K

The statement is: Consider a directed graph G of N nodes and all edges (u→v) such that u < v, find the lexicographically largest topological sort of the graph after removing a given list of edges. (nodes are numbered 1 to n)

I tried an approach which is :

First i assume a graph sorted with the initial sorting which is 1,2,3,.....,n in array named permutation, so initially permutation[1] = 1, permutation[2] = 2, ....., permutation[n]=n.

Then this pseudocode:

loop from i=2 to i=n {

j = i //the initial index of i in permutation

while(j>1 and the edge between i and permutation[j-1] is removed) {

swap permutation[j] and permutation[j-1] //permutation[j] = i before the swap, and permutation[j-1] = i after the swap j = j-1 //the new index of i in permutation

}

}

The final answer is represented by the elements of permutation, for example if n=3 and permutation is finally: permutation[1] = 3, permutation[2] = 1, permutation[3] = 2, so the topological sort here is: 3,1,2.

But the code has a wrong answer in some test which i can't view, what do you think is wrong in this approach ?

link of code:

Thanks