Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Reverse Edges

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
17 upvotes
Asked in companies
SamsungAccoliteNutanix

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 )
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
Full screen
Console