The lexicographically largest topological sort of a given graph?

Revision en2, by mohamedeltair, 2017-07-03 04:55:54

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 ?

https://ideone.com/XMwVRp

Thanks

#### History

Revisions

Rev. Lang. By When Δ Comment
en2 mohamedeltair 2017-07-03 04:55:54 14
en1 mohamedeltair 2017-07-03 04:55:07 1348 Initial revision (published)