Accepted java dfs solution


  • 0
    F
    class Solution {
        public boolean canFinish(int numCourses, int[][] pre) {
            HashMap<Integer, ArrayList<Integer>> hm = new HashMap<Integer,ArrayList<Integer>>();
            for(int i=0; i < pre.length;++i){
                int c = pre[i][0];
                int p = pre[i][1];
                if(hm.get(p)!=null) hm.get(p).add(c);
                else{
                    ArrayList<Integer> temp = new ArrayList<Integer>();
                    temp.add(c);
                    hm.put(p,temp);
                }
            }
            boolean []visited = new boolean[numCourses];
            boolean []anc = new boolean[numCourses];
            for(Integer i : hm.keySet()){
                if(dfs(hm,visited,anc,i)) return false;
            }
            return true;
        }
        public boolean dfs(HashMap<Integer, ArrayList<Integer>> hm, boolean []visited, boolean []anc,int v){
            if(!visited[v] && hm.get(v) != null){
                visited[v] = true;
                anc[v] = true;
                ArrayList<Integer> child = hm.get(v);
                for(int i=0; i < child.size(); ++i){
                    if(!visited[child.get(i)]){
                        if(dfs(hm,visited,anc,child.get(i))) return true;
                    }else{
                        if(anc[child.get(i)]) return true;
                    }
                }
            }
            anc[v] = false;
            return false;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.