Problem statement

There is a bidirectional graph with n vertices labelled 0..n-1 and an edge list edges. Determine whether there is a valid path from source to destination.

Example 1

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true

Example 2

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false

Constraints

• 1 <= n <= 15
• 0 <= edges.length <= 40
• 0 <= source, destination < n

Hints for Find if Path Exists in Graph

1. Hint 1

   BFS/DFS from source, or Union-Find.

2. Hint 2

   With Union-Find the answer is just find(source) == find(destination).

How to solve Find if Path Exists in Graph

Reachability in an undirected graph is just "is destination in the connected component of source". Build an adjacency list, then flood-fill from source and see whether you ever land on destination.

Approach

1. Answer true immediately if source == destination — the empty path counts.
2. Build an adjacency list, adding each edge in both directions since the graph is undirected.
3. Traverse from source with a stack (DFS) or queue (BFS), marking each node seen when it is pushed.
4. Return true the moment destination is reached.
5. If the traversal drains without finding it, the two nodes are in different components — return false.

Why it works

Marking on push means every node enters the frontier at most once, so the traversal terminates and visits exactly the component containing source. Reachability in an undirected graph is symmetric and transitive, so being in that component is the same as a path existing. Union-Find gives the same answer even more directly: unite every edge, then ask whether the two nodes share a root.

Complexity

• Time — O(n + m)
• Space — O(n + m)

Pitfalls

• Add both directions for each edge. Treating the list as directed silently gives wrong false answers.
• Handle source == destination explicitly — with n = 1 and no edges the answer is still true.
• The input may contain self-loops and duplicate edges; the seen check absorbs both.
• Marking as seen on pop instead of push can blow the frontier up on dense graphs.

Reference solution

Python

from typing import List

def validPath(n: int, edges: List[List[int]], source: int, destination: int) -> bool:
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for a, b in edges:
        parent[find(a)] = find(b)
    return find(source) == find(destination)

Java

public static boolean validPath(int n, int[][] edges, int source, int destination) {
    if (source == destination) return true;
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<Integer>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    boolean[] seen = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(source);
    seen[source] = true;
    while (!stack.isEmpty()) {
        int u = stack.pop();
        if (u == destination) return true;
        for (int v : adj.get(u)) {
            if (!seen[v]) {
                seen[v] = true;
                stack.push(v);
            }
        }
    }
    return false;
}

C++

bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
    if (source == destination) return true;
    vector<vector<int>> adj(n);
    for (const auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    vector<bool> seen(n, false);
    vector<int> stack;
    stack.push_back(source);
    seen[source] = true;
    while (!stack.empty()) {
        int u = stack.back();
        stack.pop_back();
        if (u == destination) return true;
        for (int v : adj[u]) {
            if (!seen[v]) {
                seen[v] = true;
                stack.push_back(v);
            }
        }
    }
    return false;
}

JavaScript

var validPath = function(n, edges, source, destination) {
    const parent = [];
    for (let i = 0; i < n; i++) parent.push(i);
    function find(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    for (const e of edges) {
        parent[find(e[0])] = find(e[1]);
    }
    return find(source) === find(destination);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More breadth-first search problems

• Find Champion II Easy
• Find Champion I Easy
• Find the Town Judge Easy
• Find Center of Star Graph Easy
• Minimize Maximum Component Cost Medium
• Minimum Time for K Connected Components Medium