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.
Example 1:
Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2: – 0 → 1 → 2 – 0 → 2
Example 2:
Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5 Output: false
Output: false
Explanation: There is no path from vertex 0 to vertex 5.
Constraints:
1 <= n <= 2 * 1050 <= edges.length <= 2 * 1050 <= ui, vi <= n - 1ui != vi0 <= source, destination <= n - 1- There are no duplicate edges.
- There are no self edges.
Approach
- Build the Graph, Convert edges into a graph using a map where each node stores its neighbors.
- Use DFS to explore, Start DFS from source.
- Track visited nodes: Maintain a visited set to avoid revisiting nodes and infinite loops.
- DFS logic
- If current node is the destination, return
true. - Visit all unvisited neighbors recursively.
- If any recursive call returns true, propagate it upward.
- If current node is the destination, return
- DFS logic
- If DFS ends with no match Return
false.
Dry Run
Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Graph Structure (Adjacency List): 0 → [1, 2] 1 → [0] 2 → [0] 3 → [5, 4] 5 → [3, 4] 4 → [5, 3]
Initialize: visited = { } Start DFS: dfs(0) • curr = 0 • mark visited = {0} • neighbors = [1, 2]
Explore neighbor 1: dfs(1) • curr = 1 • mark visited = {0,1} • neighbors = [0] • 0 already visited →
return false Explore neighbor 2: dfs(2) • curr = 2 • mark visited = {0,1,2} • neighbors = [0] • 0 already visited →
return false All neighbors of 0 explored → no path found
Final Answer: false Output: false
var validPath = function(n, edges, source, destination) {
let map = {};
for(let [x, y] of edges) {
if(!map[x]) map[x] = [];
if(!map[y]) map[y] = [];
map[x].push(y);
map[y].push(x);
}
let q = [source];
let visited = new Set();
let dfs = (curr) => {
if(curr === destination){
return true;
}
visited.add(curr);
for(let neighbor of map[curr]) {
if(!visited.has(neighbor)) {
if(dfs(neighbor)){
return true;
}
}
}
return false;
}
return dfs(source);
};
# Python
from typing import List
def validPath(n: int, edges: List[List[int]], source: int, destination: int) -> bool:
if source == destination:
return True
graph = [[] for _ in range(n)]
for x, y in edges:
graph[x].append(y)
graph[y].append(x)
visited = set()
def dfs(curr):
if curr == destination:
return True
visited.add(curr)
for nb in graph[curr]:
if nb not in visited:
if dfs(nb):
return True
return False
return dfs(source)
import java.util.*;
class Solution {
private boolean dfs(int curr, int dest, List[] graph, boolean[] visited) {
if (curr == dest) return true;
visited[curr] = true;
for (int nb : graph[curr]) {
if (!visited[nb] && dfs(nb, dest, graph, visited)) return true;
}
return false;
}
public boolean validPath(int n, int[][] edges, int source, int destination) {
if (source == destination) return true;
List[] graph = new ArrayList[n];
for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>();
for (int[] e : edges) {
graph[e[0]].add(e[1]);
graph[e[1]].add(e[0]);
}
boolean[] visited = new boolean[n];
return dfs(source, destination, graph, visited);
}
}
#include <vector>
using namespace std;
bool dfs(int curr, int destination, vector>& graph, vector& visited) {
if (curr == destination) return true;
visited[curr] = 1;
for (int nb : graph[curr]) {
if (!visited[nb] && dfs(nb, destination, graph, visited)) return true;
}
return false;
}
bool validPath(int n, vector>& edges, int source, int destination) {
if (source == destination) return true;
vector> graph(n);
for (auto &e : edges) {
graph[e[0]].push_back(e[1]);
graph[e[1]].push_back(e[0]);
}
vector visited(n, 0);
return dfs(source, destination, graph, visited);
}
#include <stdlib.h>
int validPath(int n, int **edges, int m, int source, int destination) {
if (source == destination) return 1;
// 1) degree count
int *deg = (int*)calloc(n, sizeof(int));
for (int i = 0; i < m; ++i) {
int a = edges[i][0], b = edges[i][1];
deg[a]++; deg[b]++;
}
// 2) prefix sums -> offsets
int *offset = (int*)malloc((n + 1) * sizeof(int));
offset[0] = 0;
for (int i = 0; i < n; ++i) offset[i+1] = offset[i] + deg[i];
int total = offset[n];
// 3) adjacency flat array and cursors
int *adj = (int*)malloc(total * sizeof(int));
int *cursor = (int*)calloc(n, sizeof(int)); // counts filled per node
// fill adjacency
for (int i = 0; i < m; ++i) {
int a = edges[i][0], b = edges[i][1];
adj[offset[a] + cursor[a]] = b; cursor[a]++;
adj[offset[b] + cursor[b]] = a; cursor[b]++;
}
// 4) visited array and recursion using manual stack (to avoid recursion limits we can use stack)
char *visited = (char*)calloc(n, sizeof(char));
// use stack for DFS
int *stack = (int*)malloc(n * sizeof(int));
int top = 0;
stack[top++] = source;
while (top > 0) {
int curr = stack[--top];
if (visited[curr]) continue;
if (curr == destination) { // cleanup and return
free(deg); free(offset); free(adj); free(cursor); free(visited); free(stack);
return 1;
}
visited[curr] = 1;
int start = offset[curr], end = offset[curr+1];
for (int i = start; i < end; ++i) {
int nb = adj[i];
if (!visited[nb]) stack[top++] = nb;
}
}
free(deg); free(offset); free(adj); free(cursor); free(visited); free(stack);
return 0;
}
using System;
using System.Collections.Generic;
public class Solution {
private bool Dfs(int curr, int dest, List[] graph, bool[] visited) {
if (curr == dest) return true;
visited[curr] = true;
foreach (int nb in graph[curr]) {
if (!visited[nb] && Dfs(nb, dest, graph, visited)) return true;
}
return false;
}
public bool ValidPath(int n, int[][] edges, int source, int destination) {
if (source == destination) return true;
List[] graph = new List[n];
for (int i = 0; i < n; i++) graph[i] = new List();
foreach (var e in edges) {
graph[e[0]].Add(e[1]);
graph[e[1]].Add(e[0]);
}
bool[] visited = new bool[n];
return Dfs(source, destination, graph, visited);
}
}
