Java 8ms DFS Solution


  • 0
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int [] res = new int[numCourses];
        List<Integer> order = new ArrayList<>();
        List[] parents = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            parents[i] = new ArrayList<Integer>();
        }
        for (int[] prereq: prerequisites) {
            parents[prereq[0]].add(prereq[1]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (!genOrder(numCourses, parents, i, order, new boolean[numCourses] )) {
                return new int[0]; 
            }
        }
        for (int i = 0; i < numCourses; i++) {
            res[i] = order.get(i);
        }
        return res;
    }
    public boolean genOrder(int n, List[] parents, int i, List<Integer> order, boolean[] visited) {
        if (parents[i] == null) {
            return true;
        }
        if (visited[i]) { // check cycle
            return false; 
        }
        visited[i] = true;
        if (parents[i] == null) return true;
        List<Integer> myParents = parents[i];
        for (int paren: myParents) {
            if (!genOrder(n, parents, paren, order, visited)) return false;
        }
        visited[i] = false;
        order.add(i);
        parents[i] = null; // mark the checked courses
        return true;
    }

Log in to reply
 

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