Design Gurus Logo
Find if Path Exists in Graph (easy)

Problem Statement

Given an undirected graph, represented as a list of edges. Each edge is illustrated as a pair of integers [u, v], signifying that there's a mutual connection between node u and node v.

This input format is an edge list, which is covered in the Graph Representations lesson. An edge list is compact to write down but slow to search, so the usual first step is to turn it into an adjacency list in one pass, and then run a traversal over that.

You are also given starting node start, and a destination node end, return true if a path exists between the starting node and the destination node. Otherwise, return false.

Examples

Example 1:

  • Input: n = 4, edges = [[0,1],[1,2],[2,3]], start = 0, end = 3
Image
  • Expected Output: true
  • Justification: There's a path from node 0 -> 1 -> 2 -> 3.

Example 2:

  • Input: n = 4, edges = [[0,1],[2,3]], start = 0, end = 3
Image
  • Expected Output: false
  • Justification: Nodes 0 and 3 are not connected, so no path exists between them.

Example 3:

  • Input: n = 5, edges = [[0,1],[3,4]], start = 0, end = 4
Image
  • Expected Output: false
  • Justification: Nodes 0 and 4 are not connected in any manner.

Constraints:

  • 1 <= n <= 2 * 10<sup>5</sup>
  • 0 <= edges.length <= 2 * 10<sup>5</sup>
  • edges[i].length == 2
  • 0 <= u<sub>i</sub>, v<sub>i</sub> <= n - 1
  • u<sub>i</sub> != v<sub>i</sub>
  • 0 <= source, destination <= n - 1
  • There are no duplicate edges.
  • There are no self edges.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Unlock this and all other premium problems.
No code editor for this lesson
This lesson focuses on concepts and theory