LintCode - Course Schedule II

There are a total of n courses you have to take, labeled from0ton - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:[0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example

Given n =2, prerequisites =[[1,0]]
Return[0,1]

Given n = 4, prerequisites =[1,0],[2,0],[3,1],[3,2]]
Return[0,1,2,3]or[0,2,1,3]

Analysis

First of all, this is basically a directed graph. The traps we are facing here is that the starting courses ( the ones without any prerequisites) might not be node 0; they are the nodes with 0 degree. This is the first mistake I made. I thought course 0 is automatically the first course to start. Secondly, how to deal with courses' prerequisites never got fulfilled issue (ie, circular dependency). It's clear that when there is circular dependencies, the degree of the edges can never be 0; therefore we can use a counter to count number of the courses in the result; if it's not equal to number of total courses, we know there is some issue with courses' prerequisites.

Solution

public int[] findOrder(int numCourses, int[][] prerequisites) {

        int[] results = new int[numCourses];
        if (numCourses == 0) {
            return results;
        }
        List[] allEdges = new ArrayList[numCourses];
        int[] degrees = new int[numCourses];

        for (int i = 0; i < allEdges.length; i++) {
            allEdges[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < prerequisites.length; i++) {
            degrees[prerequisites[i][0]]++;
            allEdges[prerequisites[i][1]].add(prerequisites[i][0]);
        }
        Queue<Integer> queue = new LinkedList<Integer>();

        for (int i = 0; i < degrees.length; i++) {
            if (degrees[i] == 0) {
                queue.offer(i);
            }
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                int nodeIndex = queue.poll();
                results[count++] = nodeIndex;

                List<Integer> edges = allEdges[nodeIndex];
                for (Integer edge : edges) {
                    degrees[edge]--;
                    if (degrees[edge] == 0) {
                        queue.offer(edge);
                    }
                }
                if (count > numCourses) {
                    return new int[0];
                }
                size--;
            }
        }

        if (count == numCourses){
            return results;
        } else {
            return new int[0];
        }
    }