Reverse Edges

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
18 upvotes
Asked in companies
BNY MellonSamsungAccolite

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4 3
0 3
0 1
0 2
3 2
5 4
0 4
0 1
1 3
4 1
2 0
Sample Output 1:
1 
1
Explanation For Sample Input 1:
Test Case 1 :  
The given graph is shown below.

1

Starting node = 0 and Ending node = 3. 
We can reverse edge 3 -> 2 to make a valid path of 0 -> 2 -> 3. 
So, the minimum number of operations required will be 1.

Test Case 2 : 
The given graph is shown below.

2

Starting node = 0 and Ending node = 4. 
We can reverse edge 4 -> 1 to make a valid path of 0 -> 1 -> 4. 
So the minimum number of operations required will be 1.
Sample Input 2:
2
5 4
0 4
0 1
0 2
2 3
4 3
6 6
0 5
0 1
0 2
2 3
2 4
4 5
5 3
Sample Output 2:
1
0
Hint

Assign weight 1 to all edges which you have reversed and calculate the shortest path from starting node to ending node.

Approaches (1)
Dijkstra algorithm

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.
Time Complexity

O(M * log (N)), where ‘N’ is the total number of nodes and ‘M’ is the total number of edges in the graph.

 

Here, building a graph takes O(M) time as we need to add ‘M’ edges to the graph. Also, our dijkstra algorithm takes O(M * log (N) ) as we need to visit all M edges and update distance M times. Also erasing an element from the set takes O( log(N) ) time, and we need to do this O(M) time in the worst case.

 

Hence, the overall time complexity will be O(M * log(N) ) + O(M) = O(M * log (N) ).

Space Complexity

O(N + M), where ‘N’ is the total number of nodes and ‘M’ is the total number of edges in the graph.

 

We are using a distance array that takes O(N) space. Also, our set data structure requires O(N) space as we can have at most ‘N’ vertices in the set. Also, we are using an adjacency list that takes O(M) space as we need to insert ‘M’ edges into the list. 


Hence, the overall space complexity will be O(N) + O(N)  + O(M) = O(N + M).

Code Solution
(100% EXP penalty)
Reverse Edges
Full screen
Console