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 the edges list into an adjacency list map so you can quickly find all neighbors of any node.
- Initialize BFS, Start a queue with the source node and mark it as visited.
- Traverse Level-by-Level:
- Repeatedly take a node from the queue.
- If it is the destination, return true.
- Otherwise, push all its unvisited neighbors into the queue and mark them visited.
- Repeatedly take a node from the queue.
- If BFS Ends:
- If the queue becomes empty and destination is never found, 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: queue = [0] visited = {0} Start BFS → curr = 0 → neighbors = [1, 2] → visit 1 → queue = [1],
visited = {0,1} → visit 2 → queue = [1,2],
visited = {0,1,2} → curr = 1 → neighbors = [0] → 0 already
visited → curr = 2 → neighbors = [0] → 0 already
visited No more nodes left in queue. Destination 5 not reached.
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();
visited.add(source);
while(q.length) {
let curr = q.shift();
if(curr === destination){
return true;
}
for(let neighbor of map[curr]) {
if(!visited.has(neighbor)) {
q.push(neighbor);
visited.add(neighbor);
}
}
}
return false;
};
from collections import defaultdict, deque
def validPath(n, edges, source, destination):
if source == destination:
return True
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
visited = [False] * n
q = deque([source])
visited[source] = True
while q:
cur = q.popleft()
if cur == destination:
return True
for nei in graph[cur]:
if not visited[nei]:
visited[nei] = True
q.append(nei)
return False
# Example:
# print(validPath(6, [[0,1],[0,2],[3,5],[5,4],[4,3]], 0, 5)) # False
import java.util.*;
public class Solution {
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) {
int a = e[0], b = e[1];
graph[a].add(b);
graph[b].add(a);
}
boolean[] visited = new boolean[n];
Queue q = new LinkedList<>();
q.add(source);
visited[source] = true;
while (!q.isEmpty()) {
int cur = q.poll();
if (cur == destination) return true;
for (int nei : graph[cur]) {
if (!visited[nei]) {
visited[nei] = true;
q.add(nei);
}
}
}
return false;
}
// Example usage:
public static void main(String[] args) {
Solution s = new Solution();
int n = 6;
int[][] edges = {{0,1},{0,2},{3,5},{5,4},{4,3}};
System.out.println(s.validPath(n, edges, 0, 5)); // false
}
}
#include <vector>
#include <queue>
using namespace std;
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);
queue q;
q.push(source);
visited[source] = 1;
while (!q.empty()) {
int cur = q.front(); q.pop();
if (cur == destination) return true;
for (int nei : graph[cur]) {
if (!visited[nei]) {
visited[nei] = 1;
q.push(nei);
}
}
}
return false;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int validPath(int n, int **edges, int m, int source, int destination) {
if (source == destination)
return 1;
// Step 1: Count degree of each node
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]++;
}
// Step 2: Allocate adjacency list
int **adj = (int **)malloc(n * sizeof(int *));
for (int i = 0; i < n; ++i) {
if (deg[i] > 0)
adj[i] = (int *)malloc(deg[i] * sizeof(int));
else
adj[i] = NULL;
}
// Step 3: Fill adjacency list
int *idx = (int *)calloc(n, sizeof(int));
for (int i = 0; i < m; ++i) {
int a = edges[i][0], b = edges[i][1];
adj[a][idx[a]++] = b;
adj[b][idx[b]++] = a;
}
// Step 4: BFS setup
char *vis = (char *)calloc(n, sizeof(char));
int *queue = (int *)malloc(n * sizeof(int));
int head = 0, tail = 0;
queue[tail++] = source;
vis[source] = 1;
// Step 5: BFS traversal
while (head < tail) {
int cur = queue[head++];
if (cur == destination) {
// Free all allocated memory
for (int i = 0; i < n; i++)
if (adj[i]) free(adj[i]);
free(adj);
free(deg);
free(idx);
free(vis);
free(queue);
return 1;
}
for (int i = 0; i < deg[cur]; ++i) {
int nei = adj[cur][i];
if (!vis[nei]) {
vis[nei] = 1;
queue[tail++] = nei;
}
}
}
// Cleanup
for (int i = 0; i < n; i++)
if (adj[i]) free(adj[i]);
free(adj);
free(deg);
free(idx);
free(vis);
free(queue);
return 0;
}
using System;
using System.Collections.Generic;
public class Solution {
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) {
int a = e[0], b = e[1];
graph[a].Add(b);
graph[b].Add(a);
}
bool[] visited = new bool[n];
Queue q = new Queue();
q.Enqueue(source);
visited[source] = true;
while (q.Count > 0) {
int cur = q.Dequeue();
if (cur == destination) return true;
foreach (int nei in graph[cur]) {
if (!visited[nei]) {
visited[nei] = true;
q.Enqueue(nei);
}
}
}
return false;
}
// Example usage:
public static void Main() {
var sol = new Solution();
int n = 6;
int[][] edges = new int[][] {
new int[]{0,1}, new int[]{0,2}, new int[]{3,5}, new int[]{5,4}, new int[]{4,3}
};
Console.WriteLine(sol.ValidPath(n, edges, 0, 5)); // False
}
}
