Leetcode 207) Course Schedule

20 Oct 2021 in Algorithms

My Answer

class Solution {
    Map<Integer,Set<Integer>> m;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //reconstruct prerequisites array to map,
        //initialize a map
        m = new HashMap<>();
        //make prerequisites array
        for(int i=0;i<prerequisites.length;i++){
            if(m.containsKey(prerequisites[i][0])){
                m.get(prerequisites[i][0]).add(prerequisites[i][1]);
            }else{
                m.put(prerequisites[i][0],new HashSet<>(Arrays.asList(prerequisites[i][1])));
            }
        } 
        //  System.out.println(m);
        int[] visited = new int[numCourses];

        //visited array 
        for(int i =0;i<visited.length;i++){
            visited[i]=-1;
        }

        //dfs 하기. 세가지 state , visited : 1(unlinked node를 위해서), in process : 0, unvisited : -1)
        for(int i=0;i<visited.length;i++){
            if(m.containsKey(i)){
                if(!dfs(i,visited)){
                    return false;
                }
            }
            visited[i]=1;

        }
        return true;
    }

    public boolean dfs(int i, int[] visited){
        if(visited[i]!=-1){
            return true;}

        visited[i]=0;//0 == in process
        for(int a : m.get(i)){
            if(visited[a]==0){
                return false;
            }else{
                if(m.containsKey(a)){
                    if(!dfs(a,visited)){
                        return false;
                    }
                }
            }    
            visited[a]=1;   
        }
        return true;
    }
}

Other Answer