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
class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        Map<Integer, Set<Integer>> nodeChildrenMap = new HashMap<>();
        for (int[] edge : edges) {
            nodeChildrenMap.putIfAbsent(edge[0], new HashSet<>());
            nodeChildrenMap.get(edge[0]).add(edge[1]);
            nodeChildrenMap.putIfAbsent(edge[1], new HashSet<>());
            nodeChildrenMap.get(edge[1]).add(edge[0]);
        }
        return dfs(source, destination, nodeChildrenMap, new HashSet<>());
    }

    private boolean dfs(int curr, int dest, Map<Integer, Set<Integer>> nodeChildrenMap, Set<Integer> visited) {
        if (curr == dest) {
            return true;
        }
        visited.add(curr);
        for (int child : nodeChildrenMap.get(curr)) {
            if (!visited.contains(child) && dfs(child, dest, nodeChildrenMap, visited)) {
                return true;
            }
        }
        return false;
    }
}

简单的dfs.

时间复杂度: O(n)
空间复杂度: O(n)

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
class Solution {
    private static class UnionFind {
        int[] parent;
        int[] rank;

        private UnionFind(int size) {
            parent = new int[size];
            rank = new int[size];
            for (int i = 0; i < parent.length; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

        private int find(int x) {
            if (x == parent[x]) {
                return x;
            }
            return parent[x] = find(parent[x]);
        }

        private void union(int x, int y) {
            int xRoot = find(x);
            int yRoot = find(y);
            if (xRoot != yRoot) {
                if (rank[xRoot] < rank[yRoot]) {
                    parent[xRoot] = yRoot;
                } else if (rank[xRoot] > rank[yRoot]) {
                    parent[yRoot] = xRoot;
                } else {
                    parent[yRoot] = xRoot;
                    rank[xRoot] += 1;
                }
            }
        }

        private boolean isConnected(int x, int y) {
            return find(x) == find(y);
        }
    }

    public boolean validPath(int n, int[][] edges, int source, int destination) {
        UnionFind uf = new UnionFind(n);
        for (int[] edge : edges) {
            uf.union(edge[0], edge[1]);
        }
        return uf.isConnected(source, destination);
    }
}

Union Find.