leetcode-面试题 04.01. 节点间通路

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
class Solution {
    List<Set<Integer>> g = new ArrayList<>();
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        for (int i = 0; i < n; i++) {
            g.add(new HashSet<Integer>());
        }

        for (int[] arr :
                graph) {
            g.get(arr[0]).add(arr[1]);
        }

        return dfs(n, start, start, target);
    }

    public boolean dfs(int n, int cur, int start, int target) {
        if (cur == target) {
            return true;
        }

        //遍历邻接矩阵
        for (Integer i: g.get(cur)) {
            boolean bool = dfs(n, i, start, target);
            if (bool) {
                return true;
            }
        }
        return false;
    }
}