My accepted solution


  • 0
    Q
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        boolean[] mark = new boolean[numCourses];
        HashMap<Integer,ArrayList<Integer>> map = new HashMap<Integer,ArrayList<Integer>>();
        for(int i=0;i<numCourses;i++){
            map.put(i,new ArrayList<Integer>());
        }
        for(int i=0;i<prerequisites.length;i++){
            map.get(prerequisites[i][0]).add(prerequisites[i][1]);
        }
        for(Map.Entry<Integer,ArrayList<Integer>> x:map.entrySet()){
            if(!mark[x.getKey()] && !DFS(x.getKey(),x.getValue(),mark,map,new HashSet<Integer>())) return false;
        }
        return true;
    }
    public boolean DFS(int start,ArrayList<Integer> neighbors,boolean[] mark,HashMap<Integer,ArrayList<Integer>> map,HashSet<Integer> path){
        mark[start] = true;
        path.add(start);
        for(int i:neighbors){
            if(path.contains(i)) return false;
            if(!mark[i] && !DFS(i,map.get(i),mark,map,path))  return false;
        }
        path.remove(start);
        return true;
    }
    

    Convert the 2d array to a adjacent list. It is more convenient to do a DFS in a graph represented by adjacent list. Use path to keep track of the path, when track back, delete current index from the path.


Log in to reply
 

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