[/dsa/leetcode]

1971 - Find if Path Exists in Graph

Tuesday, 8 September 2026

<easy> [problem]

Build the adjacency list from the edge list, then traverse from the source and check whether the destination is reached.

{graph}

Problem

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1. The edges are given as a 2D array edges, where edges[i] = [ui, vi] denotes a bi-directional edge between ui and vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

Given edges and the integers n, source and destination, return true if there is a valid path from source to destination, or false otherwise.

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

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

Approach

Since we are given the edges array, we just have to convert the edges into a traversable adjacency list and then use either BFS or DFS to traverse it. If we reach the destination, return true; if the queue (or stack) empties before that, return false.

BFS

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source,
                   int destination) {
        vector<vector<int>> adj(n);
        for (auto& e : edges) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
        }

        queue<int> q;
        vector<bool> visited(n, false);
        visited[source] = true;
        q.push(source);
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            if (curr == destination)
                return true;

            for (int v : adj[curr]) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.push(v);
                }
            }
        }
        return false;
    }
};
  • time: O(V + E) - O(E) to build the adjacency list, then every vertex is queued once and each adjacency list is scanned once
  • space: O(V + E) - the adjacency list holds 2E entries, plus O(V) for visited and the queue

DFS

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source,
                   int destination) {
        vector<vector<int>> adj(n);
        for (auto& e : edges) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
        }

        vector<bool> visited(n, false);
        stack<int> st;
        st.push(source);
        while(!st.empty()) {
            int curr = st.top();
            st.pop();
            if(visited[curr]) continue;
            visited[curr] = true;
            if(curr == destination) return true;
            for(int v: adj[curr]) {
                if(!visited[v]) {
                    st.push(v);
                }
            }
        }
        return false;
    }
};
  • time: O(V + E) — same two passes, only the order of visits changes
  • space: O(V + E) — the adjacency list, and the stack itself can hold up to E entries
quantinium © 2026