Formatted question description: https://leetcode.ca/all/1971.html
1971. Find if Path Exists in Graph
Level
Easy
Description
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] = [u_i, v_i]
denotes a bi-directional edge between vertex u_i
and vertex v_i
. 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 start
to vertex end
.
Given edges
and the integers n
, start
, and end
, return true
if there is a valid path from start
to end
, or false
otherwise.
Example 1:
Input: n = 3, edges = [[0,1],[1,2],[2,0]], start = 0, end = 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]], start = 0, end = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.
Constraints:
1 <= n <= 2 * 10^5
0 <= edges.length <= 2 * 10^5
edges[i].length == 2
1 <= u_i, v_i <= n - 1
u_i != v_i
1 <= start, end <= n - 1
- There are no duplicate edges.
- There are no self edges.
Solution
Use hash map to store each vertex’s adjacent vertices. Then do breadth first search starting from vertex start
. If end
can be reached, return true
. Otherwise, return false
.
class Solution {
public boolean validPath(int n, int[][] edges, int start, int end) {
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
for (int[] edge : edges) {
int node0 = edge[0], node1 = edge[1];
List<Integer> list0 = map.getOrDefault(node0, new ArrayList<Integer>());
List<Integer> list1 = map.getOrDefault(node1, new ArrayList<Integer>());
list0.add(node1);
list1.add(node0);
map.put(node0, list0);
map.put(node1, list1);
}
boolean[] visited = new boolean[n];
Queue<Integer> queue = new LinkedList<Integer>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int node = queue.poll();
if (node == end)
return true;
List<Integer> list = map.getOrDefault(node, new ArrayList<Integer>());
for (int next : list) {
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}
}
}
return false;
}
}