This is a problem in a past contest and its link is:
http://mirror.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
