Find if Path Exists in Graph

Easy·Tagsgraphbfsdfs

Problem Statement

There is a bi-directional graph with `n` vertices, where each vertex is labeled from `0` to `n - 1` (inclusive). The edges in the graph are represented as a 2D integer array `edges`, where each `edges[i] = [ui, vi]` denotes a bi-directional edge between vertex `ui` and vertex `vi`. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. You want to determine if there is a valid path that exists from vertex `source` to vertex `destination`. Given `edges` and the integers `n`, `source`, and `destination`, return `true` if there is a valid path from `source` to `destination`, or `false` otherwise.

Examples

Example 1

Input

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

Graph

Output

"true"

Why

There are two paths from vertex 0 to vertex 2: 0 -> 1 -> 2, and 0 -> 2 directly. Since a path exists, we return true.

Example 2

Input

n: 6, edges: [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]], source: 0, destination: 5

Graph

Output

"false"

Why

There is no path connecting vertex 0 and vertex 5. They belong to two completely disconnected components.

Constraints

•1 <= n <= 2 * 10^5
•0 <= edges.length <= 2 * 10^5
•edges[i].length == 2
•0 <= ui, vi <= n - 1
•ui != vi
•0 <= source, destination <= n - 1
•There are no duplicate edges.

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

An `edge list` is very hard to search through efficiently. The first thing you should do is convert the `edges` array into an `Adjacency List`. Since the graph is bi-directional, for an edge `[u, v]`, make sure to add `v` to `u`'s list, AND add `u` to `v`'s list.

Hint 2

Once you have an Adjacency List, you can traverse the graph using Breadth-First Search (BFS) or Depth-First Search (DFS) starting from the `source` vertex.

Hint 3

Graphs can have cycles! (e.g., A -> B -> C -> A). If you aren't careful, your traversal will run in an infinite loop. Use a `visited` array or Set to keep track of vertices you have already processed.

Hint 4

If your traversal ever pops the `destination` vertex off the queue or stack, you can immediately return `true`. If the traversal completely finishes and empties the queue without ever seeing `destination`, return `false`.