Find If Path Exists in Graph

Given an undirected graph with n nodes and an edge list, determine whether a path exists between the source and the destination. Pattern focus: Directed vs Undirected. Recognize that the input graph is undirected, so every edge can be traversed in both directions.

Input Format

n = number of nodes, edges = undirected edge list, source = start node, destination = target node

Output Format

true if a path exists, otherwise false

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • n, edges, source, destination must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

n = 3
edges = [[0,1],[1,2]]
source = 0
destination = 2

Output:

true

Explanation:

A path 0 -> 1 -> 2 exists.

Example 2:

Input:

n = 4
edges = [[0,1],[2,3]]
source = 0
destination = 3

Output:

false

Explanation:

The graph has two separate components.

Loading...
Find If Path Exists in Graph