207. Course Schedule!

class Solution {
    // mark the course if has been visited to avoid redundant calculation
    boolean[] courseVisited;
    // mark the path in dfs, if true, a circle is detected
    boolean[] pathVisited;
    boolean hasCircle;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 1. convert input to graph;
        // 2. search if there is a circle in the graph;
        // 3. backtrack and dfs
        // 4. cache visited nodes
        
        courseVisited = new boolean[numCourses];
        pathVisited = new boolean[numCourses];
        
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        for(int i=0; i<numCourses; i++){
            detectCircle(i, graph);
        }
        return !hasCircle;
    }
    private void detectCircle(int course, List<Integer>[] graph){
        // remember: first check if there is a circle before checking if the courseVisited!
        if(pathVisited[course]){
            hasCircle = true;
            return;
        }
        if(hasCircle || courseVisited[course] || graph[course]==null) return;
        
        courseVisited[course] = true;
        pathVisited[course] = true;
        List<Integer> requiredCourses = graph[course];
        for(int requiredCourse: requiredCourses){
            detectCircle(requiredCourse, graph);
        }
        pathVisited[course]=false;
    }
    
    private List<Integer>[] buildGraph(int numCourses, int[][] prerequisite){
        List<Integer>[] graph = new LinkedList[numCourses];
        for(int[] required: prerequisite){
            int course = required[0];
            int requiredCourse = required[1];
            if(graph[course]==null){
                graph[course]=new LinkedList();
            }
            graph[course].add(requiredCourse);
        }
        return graph;
    }
}