-
Notifications
You must be signed in to change notification settings - Fork 0
/
Find if path exists.java
36 lines (32 loc) · 1.28 KB
/
Find if path exists.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
https://leetcode.com/problems/find-if-path-exists-in-graph/
class Solution {
public boolean validPath(int n, int[][] edges, int source, int destination) {
//Store all edges in 'graph'.
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
int a = edge[0], b = edge[1];
graph.computeIfAbsent(a, val -> new ArrayList<Integer>()).add(b);
graph.computeIfAbsent(b, val -> new ArrayList<Integer>()).add(a);
}
// Store all the nodes to be visited in 'queue'.
boolean[] seen = new boolean[n];
seen[source] = true;
Queue<Integer> queue = new LinkedList<>();
queue.offer(source);
while (!queue.isEmpty()) {
int currNode = queue.poll();
if (currNode == destination) {
return true;
}
// For all the neighbors of the current node, if we haven't visit it before,
// add it to 'queue' and mark it as visited.
for (int nextNode : graph.get(currNode)) {
if (!seen[nextNode]) {
seen[nextNode] = true;
queue.offer(nextNode);
}
}
}
return false;
}
}