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

Problem of the day

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

```
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
```

```
2
4 3
0 3
0 1
0 2
3 2
5 4
0 4
0 1
1 3
4 1
2 0
```

```
1
1
```

```
Test Case 1 :
The given graph is shown below.
```

```
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.
```

```
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.
```

```
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
```

```
1
0
```