210. Course Schedule II!

DFS postorder traversal

class Solution {
    boolean[] visited;
    boolean[] isVisitedOnPath;
    boolean hasCircle;
    List<Integer> result;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 1.check if there is circle in graph, otherwise dfs will not end
        isVisitedOnPath = new boolean[numCourses];
        visited= new boolean[numCourses];
        result = new LinkedList<>();

        List<Integer>[] graph=buildGraph(numCourses, prerequisites);
        for(int i=0; i<numCourses; i++){
            dfs(i, graph);
        }
        //invalid 
        if(hasCircle) return new int[0];
        
        int[] intResult = new int[numCourses];
        for(int i=0; i<numCourses; i++){
            intResult[i]=result.get(i);
        }
        
        return intResult;
    }
    
    private void dfs(int numCourses, List<Integer>[] graph){
        if(isVisitedOnPath[numCourses]){
            hasCircle=true;
            return;
        }
        if(visited[numCourses]) return;
        
        visited[numCourses]=true;
        isVisitedOnPath[numCourses] = true;
        
        List<Integer> neighbors = graph[numCourses];
        for(int neighbor: neighbors){
            dfs(neighbor, graph);
        }
        result.add(numCourses);
        isVisitedOnPath[numCourses]=false;
    }
    
    private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites){
        List<Integer>[] graph = new LinkedList[numCourses];
        // initialize
        for(int i=0; i<numCourses;i++){
            graph[i]=new LinkedList();
        }
        
        for(int[] relation: prerequisites){
            int from = relation[0];
            int to = relation[1];
            graph[from].add(to);
        }
        return graph;
    }
}