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
Auto comment: topic has been updated by mohamedeltair (previous revision, new revision, compare).
why not just change ur queue to priority_queue
please, illustrate more
so say for the normal top sort, u implement it with queue, right?
then why not change the queue to priority_queue sorted by the specific key
first of all, it still saitisfy "toplogical" coz literally u are still implementing topsort, u just change the order of "same level" verticies.
Secondly, they are sorted as the order u want
therefore, u solve it.
I wrote the code link in the post (didn't use queue)
note that N (number of nodes) is up to 10^5, and as the problem statement says, the graph has initially N(N-1)/2 edges, and the number of edges removed is up to 10^5, so the number of edges remaining can be quite large
It is an
idea i think
what i understood from you is doing the algorithm of topo sort but instead of using queue use priority queue (so whenever can insert more than one vertex in the answer insert the largest index), but what i am talking about is that the number of edges present can reach very large number (up to (1e5*(1e5-1))/2), and still the topo sort algorithms that i know require to visit all the edges present which gave me TLE in this problem.
Why not to sort adj list itself?
if you mean the adj vector in the code i posted, so it is just vector of sets where adj[i] = set of nodes (sorted in ascending order of their numbers) of which their edges to node i are removed, I put them in a set to check if an edge from specific node x to node i is removed in logn, i use adj[i].find(x) to search for x, if it returned iterator other than set.end() therefore edge going from x to i is removed (since x is in adj[i]).
Sorry guys, but I didn't get an answer till now to the problem. the problem isn't whether to use a normal queue or priority queue (of course I will use priority queue to give higher priority to nodes with larger number), but the problem is that the edges present in the graph may reach very large number (1e5(1e5-1))/2.
I thought using segment tree with lazy propagation, for example I maintain array of ints, let its name be arr. and for each node i, arr[i] will be the number of nodes that need to be put in the topological sort first before putting node i (the nodes with smaller numbers than i whose edges with node i are not cut). and whenever I put a node v in the topological sort, I update the ranges of nodes with numbers greater than v (whose edges with node v are not cut) decreasing their arr values by 1 each. the problem is that after each update, how to know (in efficient time) the new nodes i whose arr[i] became 0 to place them in the priority queue ?
You may get global minimum from segment tree and its position. If it is zero then you have found arr[i]=0, if not then there aren't any yet.
Just don't foget to set used arr[i] to inf so that they won't be found again
Ok, now suppose 2 cases:
1) if in the node segment there were two or more minimums with the same value, I think this can be solved by putting in each node vector not int to represent the indices of elements having the minimum value along with another int representing this minimum value.
2) if the minimum value of a node segment became 0 after a specific update, I shall change this value to inf, but now I want to know the new minimum of the segment. to do this, I think i should recursively call the children of this node till I reach a node with minimum either not 0 or till I reach a leaf node.
am I thinking right ?
It's no good storing vectors in segment tree in this case. It will slow down updates to linear. Second one is not exactly good because you will have to be careful with the order of operations.
What I meant was to get the usual increase interval — get minimum on interval tree to support the array of in-degrees with some values in each node. One value is what the minimal value is, second is where any instance of this value on this segment is located and also you have to store all the stuff for lazy propagation.
Now when you are done changing degrees after processing the node you need to look for unprocessed vertexes with zero degree to add them to the queue. You check that minimal degree is zero and while it is you ask for any instance, set value in tree to inf and put into queue.
You are right, vectors are not needed in this case. I wrote a code for segment tree where each node represents only the minimum value for this segment. and whenever this minimum reaches 0 I recursively call the nodes' children till I reach a node whose new minimum is not 0 or I reach a leaf node (for which its minimum is 0, so I add its index to the priority queue/set and change it in the segment tree to inf, then update the ancestor nodes accordingly). It is finally accepted with good time. thank you brother for your help.
link of code:
https://ideone.com/JSqbeu