Path Reversals

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
9 upvotes
Asked in company
Tower Research Capital

Problem statement

You are given a directed graph and two nodes, ‘S’ and ‘D’, denoting the start and end node. Your task is to find the minimum number of edges that you have to reverse to find the path from nodes 'S' to 'D'.

For example:

graph1

Let's consider 'S' = 0 and 'D' = 4. In the above graph, the path from nodes 0 to 4 can be created by only reversing the edge (0, 5). Hence, the answer is 1.
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’, representing the number of nodes and edges in the graph.

The following M lines of the test case contain two space-separated integers, ‘A’ and ‘B’, representing an edge from node ‘A’ to node ‘B’.

The last line of the test case contains two space-separated integers, ‘S’ and ‘D’, denoting the start and end node.
Output Format: 
For each test case, print a single integer, i.e., the minimum number of edges to be reversed, so the path exists from ‘S’ to ‘D’.

Print the output of each test case 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
2 <= N <= 10^5
N - 1 <= M <= 10^5
0 <= A, B < N
0 <= S, D < N

Time Limit: 1 sec
Sample Input 1:
2
6 7
5 0
1 0
5 3 
2 1
2 3
5 4 
3 4
0 4
4 4
0 1
1 2
1 3
0 3
3 0
Sample Output 1:
1
1
Explanation:

graph1

For the first test case, the only edge that needs to be reversed is (5,0), so that path exists from nodes 0 to 4. Hence, the answer is 1.

graph2

For the second test case, only one edge (0, 3) needs to be reversed so that path exists from nodes 3 to 0. Hence, the answer is 1.
Sample Input 2:
2
6 5
1 0
2 3
4 1
3 5
5 1
0 4
5 4
4 1
2 0
2 1
2 4
0 4
Sample Output 2:
2
1
Hint

Try adding reverse edges. 

Approaches (2)
Bellman-Ford Algorithm

In this approach, we make the graph into a weighted graph. We set the edges’ edge-weight as 0 and add all the reverse edges with weight 1.

We will apply the Bellman-Ford algorithm on the start node and get the distance from all the nodes in the graph.  Each time a reversed edge is traversed in the path, the path cost will increase by 1.The total path cost gives the number of reversed edges used in getting the path from source to destination. 

 

We will create a function bellmanFord(edges, n, source). The parameter edge is the edge list, n is the number of nodes, and the source is the starting node. This function will return the list of distances of all nodes from the source.

 

Algorithm:

  • The function bellmanFord(edges, n, source): where the parameter edges, is the edge list, n is the number of nodes, and the source is the starting node.
    • Create a distances list of length n with all values initialized to the maximum value of the integer.
    • Set the distance of source distances[source] as 0
    • Iterate from 0 to n - 1
      • Iterate edge through the array edges
        • Set currentSource as edge[0]
        • Set destination as edge[1].
        • Set weight as edge[3].
        • Set distances[destination] as the minimum of distances[destination] and the sum of distances[currentSource] and weight.
    • After the while loop ends, return the list distances.
  • Make a list newEdges.
  • Iterate through a list of Edges, and for each edge.
    • Append 0 to edge, Append it to newEdges array.
    • Make a newEdge list as [edge[1], edge[0], 1], to make the reverse edge with weight 1. Append newEdge to newEdges.
  • Call the bellmanFord(newEdges, N, S) function, which returns the distances of all nodes from the source nodes S and stores the output as pathList.
  • We will return pathList[D]. That represents the distance of ‘S from node D.
Time Complexity

O(N*M), Where N and M are the numbers of nodes and edges in the graph.

 

We are doing N iterations, and in each iteration, we are traversing through the edges that take O(M) time. Hence, the overall time complexity becomes O(N*M).   

Space Complexity

O(N + M), Where N and M are the numbers of nodes and edges in the graph.


We are maintaining a distances array that takes O(N) space. The O(M) space complexity is used to maintain the edges array. Hence the overall space complexity becomes O(N).

Code Solution
(100% EXP penalty)
Path Reversals
Full screen
Console