1971. Find if Path Exists in Graph 

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
class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        Map<Integer, List<Integer>> edgeMap = new HashMap<>();
        for (int[] edge : edges) {
            int nodeA = edge[0], nodeB = edge[1];
            edgeMap.computeIfAbsent(nodeA, key -> new ArrayList<>()).add(nodeB);
            edgeMap.computeIfAbsent(nodeB, key -> new ArrayList<>()).add(nodeA);
        }

        Set<Integer> setA = new HashSet<>();
        setA.add(source);
        Set<Integer> setB = new HashSet<>();
        setB.add(destination);

        Set<Integer> visitedSet = new HashSet<>();

        while (!setA.isEmpty() && !setB.isEmpty()) {
            Set<Integer> nextSet = new HashSet<>();

            for (int node : setA) {
                if (setB.contains(node)) {
                    return true;
                }

                visitedSet.add(node);
                for (int nextNode : edgeMap.getOrDefault(node, Collections.emptyList())) {
                    if (!visitedSet.contains(nextNode)) {
                        nextSet.add(nextNode);
                    }
                }
            }

            setA = setB;
            setB = nextSet;
        }

        return false;
    }
}

双向 BFS，注意记录访问过的节点，避免死循环。

References

1971. Find if Path Exists in Graph