有向图的节点通路

有向图的节点通路

描述：给定有向图的边的集合，设计一个算法，找出两个节点之间是否存在一条通路。

https://leetcode-cn.com/problems/route-between-nodes-lcci/

注意：有向图大概率不可以使用并查集！！

思路：针对给定的边，使用邻接表存储每个节点可以达到的节点，然后深搜，为了避免存在环的时候走向死循环，应该标记哪些点访问过。

class Solution {
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {

        boolean[] vis = new boolean[n];
        HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
        for (int[] edge:graph){
            HashSet<Integer> set = map.getOrDefault(edge[0], new HashSet<>());
            set.add(edge[1]);
            map.put(edge[0], set);
        }
        return dfsGraph(start,target, map, vis);
    }
    public boolean dfsGraph(int start,int end, HashMap<Integer, HashSet<Integer>> map, boolean[] vis){
        if (start == end){
            return true;
        }
        Set<Integer> sets = map.get(start);
        if (sets == null || sets.isEmpty()){
            return false;
        }
        vis[start] = true;
        for(Integer n: sets){
            if (!vis[n]){
                if(dfsGraph(n, end, map, vis)){
                    return true;
                }
            }
        }
        return false;
    }
}