REVERSE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Dmytro Berezin
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu

DIFFICULTY:

Easy

PREREQUISITES:

Graph, Shortest Path Algorithms

PROBLEM:

A directed graph with N vertices and M edges is given.
What is the minimum number of edges he needs to reverse in order to have at least one path from vertex 1 to vertex N, where the vertices are numbered from 1 to N?
1 ≤ N,M ≤ 105

EXPLANATION:

Add reverse edge of each original edge in the graph. Give reverse edge a weight=1 and all original edges a weight of 0. Now, the length of the shortest path will give us the answer.

How?

If shortest path is p: it means we used k reverse edges in the shortest path. So, it will give us the answer.
The shortest path algorithm will always try to use as less reverse paths possible because they have higher weight than original edges.

To find shortest path, we can use Dijkstra’s Algorithm which works in O(|E| log |V|) if implemented using adjacency lists and priority queue.
Also, since there are only 0 and 1 weight edges, we can also do this by BFS: maintain a deque instead of a queue and add a vertex to the front of the deque if 0 edge is used and to the back of the deque otherwise.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

13 Likes

@darkshadows Could you please explain the deque solution more: what do we do after adding the edges as said?

@ambarpal
Study this - Geeks For Geeks Dijsktra Adjacency List

@ambarpal, there is not much difference between deque and queue. You take vertices from the beginning each time but to deque you can add to the beginning sometimes if the weight of edge is 0 (because there is no difference which vertices of the same level to explore firstly).

1 Like

Please help me in this code
http://www.codechef.com/viewsolution/4545769

Hi @ambarpal I have done it by BFS using a queue. Here is my solution for reference : http://www.codechef.com/viewsolution/4482761 . In the solution graph vector is the input graph and ans[i] stores the length of the shortest path from N to that node so far. It is updated if we find a shorter path. ans[1] will finally store the shortest length from n to 1.

My BFS runs as follows. Reach all the nodes u can with normal paths. If final city is reached, break. Else add 1 to cost and reach all cities you can with a reverse path from current set of cities. Here’s the code: http://www.codechef.com/viewsolution/4471282

Can someone help me in finding the bug http://www.codechef.com/viewsolution/4503656

Can someone please provide the test case where this solution is failing.http://ideone.com/7347aF

I am storing the undirected version of graph in a vector and applying dijkstra’s finding the shortest path keeping the track of the minimum number of edges to be reversed by checking if the edge (i,j) exists in the input graph(stored in a set).

Is it giving TLE because of the way of implementation?

can someone tell me the mistake in my code. Algo that i used is same as the one given in editorial(using heaps) n i got WA.

http://www.codechef.com/viewsolution/4547959

can someone tell me how we can give the weight of reverse edges as 1 when we dont how many such reverse are possible
and even if it is possible then how???

can someone tell me how we can give the weight of reverse edges as 1 when we dont how many such reverse are possible and even if it is possible then how???

can someone tell me how we can give the weight of reverse edges as 1 when we dont how many such reverse are possible and even if it is possible then how???

Maximum edges are given in the constraints: 10^5. Imagine the edges in terms of their costs. Travelling over a normal edge is 0. Inverting an edge has some cost, some constant value for all reverse edges. You can give it any value. The author has given all reverse edges a value of one because its simple to do so.

A O(V+E) algorithm: Combination of dfs and bfs. Basically in this algo we use dfs to push nodes into the bfs queue… Initially all the nodes which can be visited from vertex node 1 are pushed into the queue with level being equal to 0… Then each time we dequeue and do the dfs of all the elements(if not already visited) which can be visited by reversing the edge with this vertex(This pushes them into the queue) .The level of all these nodes will be level of the dequeued node+1…Do this until the queue empties.The level of the nth node is the answer if it is visited otherwise it is -1.

@adi_das >> for every given edge x->y, add it to the graph with weight 0 and also add a reverse edge y->x with weight 1. So if we are given E edges, after adding them and the reverse edges we will be having a total of 2*E edges, half of them with 0 weight and other half of them with weight 1. Hope this clarifies your doubt.

1 Like

i have used warshalls algorithm to find the shortest path but my solution gave a wa

i took a 2d matrix and initially i stored INF in matrix then
matrix[x][y]=0; and matrix[y][x]=1;
then i applied kruskals algo
which gave coreect answers for the given test case but wa when i submitted my solution .

A simple question how you get the thought for this like adding a reverse edge with weight 1 this makes the problem very easy. Is this a classical problem or i can use any other apporoach to solve this…please help.

the limit is 10^6, you will exceed the memory constraint, the 2D array will not be formed.

Can any one give me test cases for which my code is giving WA…

Thnx for ur help…

http://www.codechef.com/viewsolution/4491750

//