This is a problem in a past contest and its link is:↵
↵
http://codeforces.me/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:↵
↵
https://ideone.com/XMwVRp↵
↵
Thanks
↵
http://codeforces.me/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:↵
↵
https://ideone.com/XMwVRp↵
↵
Thanks
