I was trying out the chef and reversing question of August Chanllenge. During the contest, I tried out this . My logic goes the same way as finding the path in Dijkstra’s, the only difference is I am using revcnt[] as the basis of relaxing the edges. (The undirected version of the graph is stored in a vector and the input graph in a set). If an edge from i to j exists in the input graph(done by finding in the set line no 42 in the code), then revcnt[j]=revcnt[i] else, revcnt[j]=revcnt[i]+1. It gave TLE.
I used map for getting the vertex with minimum revcnt[], because map is a form of balanced binary tree and hance the order of insertion is O(logn) and the ver first entry of the map will give the required node to start with.
Seeing other’s solution, I tried the priority queue version of the same. It passed. Why is it so, because even in this the complexity is same I suppose. Then why the previous map solution gave tle.
Priority queue is faster than map.
Priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a “priority” associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.
A priority queue is an abstract concept like “a list” or “a map”; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.
So, do you mean if I dont take the priority queue in the above code to be implemented using heap, then my complexity calculations/approximations are correct…?