My DFS Java Solution (12ms)


  • 0
    G

    This is same approach as Course Schedule I with addition of stack :

    public class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            List<List<Integer>> prereqs = new ArrayList<>();
            for(int course=0;course<numCourses;course++){
                prereqs.add(course,new ArrayList<Integer>());
            }
            
            for(int i=0; i<prerequisites.length;i++){
                prereqs.get(prerequisites[i][0]).add(prerequisites[i][1]);
            }
            
            boolean[] visited = new boolean[numCourses];
            boolean[] visiting = new boolean[numCourses];
            Stack<Integer> ordered = new Stack<>();
            boolean isCycle = false;
            for(int course=0;course<numCourses;course++){
                if(!isCycle && !visited[course]){
                    isCycle = exploreOrder(prereqs,course,visited,visiting,ordered);   
                }
            }
            if(isCycle){
                return new int[0];//failed
            }
            int[] res = new int[numCourses];
    
            for(int course=numCourses-1;course>=0;course--){
                res[course] = ordered.pop();
            }
            return res;
        }
        
        public boolean exploreOrder(List<List<Integer>> prereqs,int course,boolean[] visited,boolean[] visiting, Stack<Integer> ordered){
            if(visiting[course]){
                //System.out.println("Cycle found");
                return true;
            }
            visiting[course] = true;
            List<Integer> coursePrereqs = prereqs.get(course);
            boolean isCycle = false;
            for(int prereqCourse=0; prereqCourse<coursePrereqs.size();prereqCourse++){
                if(!isCycle) isCycle=exploreOrder(prereqs,coursePrereqs.get(prereqCourse),visited,visiting,ordered);
            }
            if (!visited[course]){
                ordered.push(course);
            }
            visiting[course] = false;
            visited[course] = true;
            return isCycle;
        }
    }
    
    

Log in to reply
 

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