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 )
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.
Hint

Try to use a Depth-first search.

Approaches (2)
Depth First Search

In this approach, we are going to use DFS(Depth-first search). We have to make a visited array isVisited which checks whether the particular node number is visited or not.

Initialize all entries of the isVisited array with 0. Now we have to use the recursive function here. The first call is made on the node source, and in the recursive function, mark this node as visited and checks whether it is the node destination or not. If yes, we will return true; otherwise, we will make recursive calls on all its adjacent unvisited nodes. If any of the calls return true then return we will return true, else return false.

 

Algorithm:

  • Make a recursive function dfs(source, destination, isVisited, adjacencyList) where the source is the source node. The destination is the destination node, isVisited is the array that checks whether that node is visited or not, and adjacencyList is the adjacency list of Edges. This function returns whether there exists a path between source and destination nodes.
  • The base condition of this function is if the node which is passed as a source node is the destination node, then returns true.
  • Mark the node that is passed as an argument as visited. So, set isVisited[source] as 1.
  • Iterate node through adjacencyList[source]. 
    • We will check if isVisited[node] is equal to 1, then move to the next node.
    • We will make the recursive call on every unvisited element. If dfs(node, destination, isVisited, adjacencyList) are equal to true, we will return true.  It means there is some path from the source to the destination node.
  • Return false as we cannot reach the destination node.
  • Create a visited array isVisited initially filled with 0, of size V.
  • Create a list adjacencyList of size V.
  • Iterate index from 0 to E - 1,
    • Insert Edges[index][1] in adjacencyList[Edges[index][0]].
  • Set answer as dfs(source,destination,adjacencyList).
  • Return answer, which tells whether there exists some path from the source node to the destination node. 
Time Complexity

O(V + E) where V is the number of vertices in the graph and E is the number of edges in the graph.

 

We are traversing on each vertex and edge only one time. So, the overall time complexity is O(V + E). 

Space Complexity

O(V + E) where V is the number of vertices in the graph and E is the number of edges in the graph.

 

In the worst case, the space complexity O(V + E) is required by the adjacency list. The O(V) space is used for the visited array and recursion stack in the worst case. So, the overall space complexity is O(V + V + E) = O(V + E).

Code Solution
(100% EXP penalty)
Check If Path Exists
Full screen
Console