Java DFS double cache visiting each vertex once 433ms


  • 28
    B
    public class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            List<List<Integer>> adj = new ArrayList<>(numCourses);
            for (int i = 0; i < numCourses; i++) adj.add(i, new ArrayList<>());
            for (int i = 0; i < prerequisites.length; i++) adj.get(prerequisites[i][1]).add(prerequisites[i][0]);
            boolean[] visited = new boolean[numCourses];
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < numCourses; i++) {
                if (!topologicalSort(adj, i, stack, visited, new boolean[numCourses])) return new int[0];
            }
            int i = 0;
            int[] result = new int[numCourses];
            while (!stack.isEmpty()) {
                result[i++] = stack.pop();
            }
            return result;
        }
        
        private boolean topologicalSort(List<List<Integer>> adj, int v, Stack<Integer> stack, boolean[] visited, boolean[] isLoop) {
            if (visited[v]) return true;
            if (isLoop[v]) return false;
            isLoop[v] = true;
            for (Integer u : adj.get(v)) {
                if (!topologicalSort(adj, u, stack, visited, isLoop)) return false;
            }
            visited[v] = true;
            stack.push(v);
            return true;
        }
    }

  • 0
    G

    Your coding style is clean. I have similar solution and it works in 12ms :

    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;
        }
    }
    

  • 1
    A

    I replaced the two boolean arrays with one int array where I track the state -

    0 - denotes not visited
    1 - denotes visiting
    2 - denotes visited

    Here is the modified code:

    public int[] findOrder(int numCourses, int[][] prerequisites) {
            List<List<Integer>> adj = new ArrayList<List<Integer>>(numCourses);
            for (int i = 0; i < numCourses; i++) adj.add(i, new ArrayList<>());
            for (int i = 0; i < prerequisites.length; i++) adj.get(prerequisites[i][1]).add(prerequisites[i][0]);
            int[] visited = new int[numCourses];
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < numCourses; i++) {
                if (!topologicalSort(adj, i, stack, visited)) return new int[0];
            }
            int i = 0;
            int[] result = new int[numCourses];
            while (!stack.isEmpty()) {
                result[i++] = stack.pop();
            }
            return result;
        }
        
        private boolean topologicalSort(List<List<Integer>> adj, int v, Stack<Integer> stack, int[] visited) {
            if (visited[v] == 2) return true;
            if (visited[v] == 1) return false;
            visited[v] = 1;
            for (Integer u : adj.get(v)) {
                if (!topologicalSort(adj, u, stack, visited)) return false;
            }
            visited[v] = 2;
            stack.push(v);
            return true;
        }
    

  • 0
    L
    This post is deleted!

  • 0
    G

    Wow, nice solution! I think your solution is more elegant than the top voted!


Log in to reply
 

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