Last Updated: 25 Feb, 2021

Reverse Edges

Moderate

Asked in companies

Solve now

Problem statement

You are given a directed graph of ‘N’ nodes and ‘M’ edges. Also, you have two nodes ‘A’ and ‘B’. Your task is to make at least one valid path from ‘A’ to ‘B’ by doing the below operations a minimum number of times.

Choose two nodes ‘X’ and ‘Y’, such that there exists an edge from ‘X’ to ‘Y’.

Delete edge ‘X’ to ‘Y’.

Add edge ‘Y’ to ‘X’.

You need to print the minimum operations that you have done.

Input Format

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’ where ‘N’ denotes the total number of nodes and ‘M’ denotes the total number of edges in the graph.

The second line of each test case contains two space-separated integers ‘X’ and ‘Y’ where ‘X’ denotes the starting node of the path and ‘Y’ denotes the ending node of the path.

The next ‘M’ lines contain two space-separated integers ‘U’ and ‘V’ where ‘U’ and ‘V’ represent the nodes that share an edge from ‘U’ to ‘V’.

Output Format:

For each test case, print the minimum number of operations required to make at least one valid path from ‘A’ to ‘B’.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 3000
1 <= M <= min(3000, N*(N-1)/2)
0 <= X, Y, U, V <= N - 1

Time Limit : 1 sec

Solve now

Approaches

01 Approach

The idea here is to make the graph undirected by adding all edges in the reverse direction. We will assign weight zero to all edges that are not reversed and weight 1 to all edges that are reversed. Then we will use the Dijkstra algorithm to find the minimum weight path from starting node to the ending node to get the minimum number of operations.

For example:

Below left side directed graph will be converted into right side undirected graph

E:\coding ninjas\Phase 2\Problem 14 - Reverse edges\images\5.png

E:\coding ninjas\Phase 2\Problem 14 - Reverse edges\images\6.png

Then we will find the minimum weight path in the right-side graph using the Dijkstra algorithm.

Algorithm:

Declare the following things:
A set of pairs to keep track of minimum distance of a current node from starting node.
A distance array to keep store distances of all nodes from the source node and initialize all its elements with ‘INF’ where ‘INF’ = ‘N’ as the maximum possible distance of a node from starting node is ‘N’. Here ‘N’ is the total number of vertices in the graph.
Build an adjacency list using the edges array given in the problem.
Push source/starting node to set.
Run a loop until the set is not empty:
Find the node with minimum weight using set say, ‘U’ and erase it from the set.
Run a loop to visit all neighbors of ‘U’.
Say, the current neighbor of ‘U’ is ‘V’.
If ‘distance[V]’ > ‘distance[U]’ + weight of U
Erase pair (distance[V], V) from the set as we have found a minimum distance path to ‘V’ through ‘U’.
Update ‘distance[V]’ as ‘distance[U]’ + weight of U.
Return distance of ending node.

Solve now