Find if Path Exists in Graph

1. Define the problem

There is a bi-directional graph with n vertices, labeled from 0 to n - 1, and a list of edges, where edges_i = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Given source and destination vertices, return true if there is a path from source to destination, or false otherwise. Union every edge, then compare find(source) and find(destination) . They are connected exactly when the two roots match.

Constraints

1 ≤ n ≤ 2 × 10⁵
0 ≤ edges.length ≤ 2 × 10⁵
edges_i.length == 2
0 ≤ ui, vi ≤ n - 1
0 ≤ source, destination ≤ n - 1

Example

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

Outputtrue

Explanation There are two paths from vertex 0 to vertex 2: 0 → 1 → 2 and 0 → 2.

2. Know the words first

In plain terms

Bi-directional edge: A connection you can travel in either direction — if u connects to v, v also connects to u.

3. Visualize the solution

Union every edge, then compare roots

node 0parent 1

node 1parent 1

node 2parent 2

Statusunion

Union edge [0, 1]. Vertex 0 now points at vertex 1, so both share root 1.

What happens in this step

union(0, 1)
find(0) → 0   find(1) → 1
roots differ → union: parent[0] = 1
parent array: [0, 1, 2] → [1, 1, 2]

Vertex 0's root is attached under vertex 1's root — the two vertices now belong to the same group, represented by root 1.

Step 1 of 4

Steps to visualize

The row has one cell per vertex. Each cell shows that vertex's current parent; a vertex pointing at itself is a root.
Give every vertex its own group to start, so parent = [0, 1, 2].
Union every edge in the list, merging the two groups it connects.
Call find on source and find on destination.
If both calls return the same root, a path exists between them.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Union every edge, then compare roots

node 0parent 1

node 1parent 1

node 2parent 2

Statusunion

Union edge [0, 1]. Vertex 0 now points at vertex 1, so both share root 1.

What happens in this step

union(0, 1)
find(0) → 0   find(1) → 1
roots differ → union: parent[0] = 1
parent array: [0, 1, 2] → [1, 1, 2]

Vertex 0's root is attached under vertex 1's root — the two vertices now belong to the same group, represented by root 1.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function validPath(n, edges, source, destination) {
  const parent = Array.from({ length: n }, (_, i) => i);

  function find(x) {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }

  function union(a, b) {
    const rootA = find(a);
    const rootB = find(b);
    if (rootA !== rootB) {
      parent[rootA] = rootB;
    }
  }

  for (const [a, b] of edges) {
    union(a, b);
  }

  return find(source) === find(destination);
}

Time: O((n + e) · α(n))
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2`	`true`	example from the docstring
`n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5`	`false`	source and destination sit in two separate components
`n = 1, edges = [], source = 0, destination = 0`	`true`	source and destination are the same vertex with no edges at all
`n = 2, edges = [], source = 0, destination = 1`	`false`	two vertices with no edges between them
`n = 2, edges = [[0,1]], source = 0, destination = 1`	`true`	a single direct edge connects source and destination
`n = 5, edges = [[0,1],[1,2],[2,3],[3,4]], source = 0, destination = 4`	`true`	source and destination are connected through a longer chain of edges

Find if Path Exists in Graph