/
FindIfPathExistsInGraph.java
52 lines (42 loc) · 1.57 KB
/
FindIfPathExistsInGraph.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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// https://leetcode.com/problems/find-if-path-exists-in-graph/
class Solution {
// Normal DFS from source to destination.
// DFS algorithm.
// 1. Create a adjacency map if not already.
// 2. Create a stack and a visited set.
// 3. Add the source to the stack
public boolean validPath(int n, int[][] edges, int source, int destination) {
Map<Integer, Set<Integer>> adjacencyMap = new HashMap<>();
for (int[] edge: edges) {
int a = edge[0];
int b = edge[1];
Set<Integer> l1 = adjacencyMap.getOrDefault(a, new HashSet<>());
Set<Integer> l2 = adjacencyMap.getOrDefault(b, new HashSet<>());
l1.add(b);
l2.add(a);
adjacencyMap.put(a, l1);
adjacencyMap.put(b, l2);
}
// Start of DFS
Stack<Integer> stack = new Stack<>();
stack.add(source);
Set<Integer> visited = new HashSet<>();
visited.add(source);
while (!stack.isEmpty()) {
int last = stack.pop();
Set<Integer> neighbors = adjacencyMap.getOrDefault(last, new HashSet<>());
if (neighbors.contains(destination)) {
return true;
}
if (last == destination) {
return true;
}
for (int node: neighbors) {
if (visited.add(node)) {
stack.push(node);
}
}
}
return false;
}
}