📃 题目描述

题目链接：面试题 04.01. 节点间通路 (opens new window)

🔔 解题思路

有环图，所以需要存储已访问过的节点

class Solution {
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] item : graph) {
            int from = item[0];
            int to = item[1];

            map.putIfAbsent(from, new ArrayList<>());
            if (!map.get(from).contains(to)) {
                map.get(from).add(to);
            }
        }
        
        boolean[] used = new boolean[n];
        return dfs(start, target, map, used);
    }

    private boolean dfs(int start, int target, Map<Integer, List<Integer>> map, boolean[] used) {
        used[start] = true;

        if (start == target) {
            return true;
        }

        List<Integer> neighbors = map.get(start);
        if (neighbors == null) {
            return false;
        }
        for (int neighbor : neighbors) {
            if (!used[neighbor]) {
                // neighbor 能否到 target
                if (dfs(neighbor, target, map, used)) {
                    return true;
                }
            }
        }

        return false;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：