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

Check If Path Exists

Easy
0/40
Average time to solve is 10m
profile
Contributed by
10 upvotes
Asked in companies
AmazonGrofersGoogle

Problem statement

You are given a directed and unweighted graph of 'V' vertices and 'E' edges. All edges are given in a 2-dimensional array ‘Edges’ in which ‘Edges[i][0]’ and ‘Edges[i][1]’ contain an edge. Your task is to check if there exists a path from the vertex 'source' to 'destination'.

For Example:
Consider the number of vertices is 4 and number of edges is 3, and the array of edges is:
[ [0, 1]
  [1, 2] 
  [2, 3] ]
there exists one path between 0 and 2, which is 0 -> 1 -> 2. Hence, the answer is 'true'.
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= T <= 5
1 <= V, E <= 10 ^ 5
0 <= Edges[i][0], Edges[i][1] < V
0 <= source, destination < V

Time Limit: 1 sec
Sample Input 1:
2
3 3
0 1
1 2
1 0
0 2
4 2
1 2
0 3
0 2
Sample Output 1:
true 
false   
Explanation:
In test case 1:
In this, there are 3 vertices and 3 edges, and there is a path between 0 and 2 which is 0 -> 1 -> 2. Hence, the answer is true.

In test case 2:
In this, there are 4 vertices and 2 edges, and there is no path between 0 and 2. Hence, the answer is false.
Sample Input 2:
1
4 5
0 1
0 2
1 2
2 0
2 3
3 1
Sample Output 2:
false 
Explanation:
There are 4 vertices and 5 edges, and there is no path between 3 and 1, so our answer is false.
Full screen
Console