Problem title
Difficulty
Avg time to solve

Check whether second string can be formed from characters of first string
Easy
10 mins
Add Linked Lists
Easy
20 mins
Reachable Nodes
Easy
10 mins
Shortest Path
Moderate
25 mins
Duplicate Subtrees
Moderate
30 mins
Check If Path Exists
Easy
10 mins
Print Common Elements
Easy
15 mins
Detect Cycle in a Directed Graph
Moderate
25 mins
Braille's Dilemma
Hard
15 mins
Set K Bits
Easy
10 mins
3

Check If Path Exists

Difficulty: EASY
Contributed By
Waris |Level 1
Avg. time to solve
10 min
Success Rate
90%

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'.
Input format :
The first line of input contains an integer ‘T’, the number of test cases.

The first line of each test case contains two space-separated integers, ‘V’, and ‘E’, which denote the number of vertices and edges in the graph.

The next 'E' lines will denote the edges of the graph where every edge is defined by two space-separated integers 'Edges[i][0]’ and 'Edges[i][1]', which signifies an edge from vertex 'Edges[i][0]’ to vertex 'Edges[i][1]’.

The last line of each test case contains two integers, ‘source’ and ‘destination’.
Output Format :
For each test case, print 'true' if there exists a path from vertex 'source' to 'destination'. Otherwise, print 'false'.

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
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.
Reset Code
Full screen
copy-code
Console