Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 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.

For example:

2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices.

这道题目与Course Schedule相比要输出一个可能的结果集，如果存在环就输出一个空集。我们同样采用DFS和BFS两种方法来解决。问题在于何时记录结果，用DFS时，我们在递归完成时将当前元素加入结果集；对于BFS，每次从队列中取元素后，将元素加入结果集。代码如下：

DFS：

public class Solution {
    HashSet<Integer> isVisited;
    boolean[] onStack;
    LinkedList<Integer> list;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] result = new int[numCourses];
        if(prerequisites == null || prerequisites.length == 0) {
            for(int i = 0; i < numCourses; i++) {
                result[i] = i;
            }
            return result;
        }
        list = new LinkedList<Integer>();
        onStack = new boolean[numCourses];
        isVisited = new HashSet<Integer>();
        List<Integer>[] graph = new List[numCourses];
        for(int i = 0; i < prerequisites.length; i++) {
            int key = prerequisites[i][1];
            int value = prerequisites[i][0];
            if(graph[key] == null) graph[key] = new ArrayList<Integer>();
            graph[key].add(value);
        }
        for(int i = 0; i < numCourses; i++) {
            if(!isVisited.contains(i) && hasCycle(i, graph) == true) return new int[0];
        }
        for(int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
        
    }
    
    public boolean hasCycle(int i, List<Integer>[] graph) {
        isVisited.add(i);
        onStack[i] = true;
        boolean cycle = false;
        if(graph[i] != null) {
            for(int c : graph[i]) {
                if(!isVisited.contains(c)) {
                    cycle = hasCycle(c, graph);
                    if(cycle == true)
                    break;
                } else if(onStack[c] == true) {
                    cycle = true;
                    break;
                }
            }
        }
        list.addFirst(i);
        onStack[i] = false;
        return cycle;
    }
}

BFS：

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] result = new int[numCourses];
        if(prerequisites == null || prerequisites.length == 0) {
            for(int i = 0; i < numCourses; i++)
                result[i] = i;
            return result;
        }
        int edges = prerequisites.length;
        int start = 0;
        int[] getIndex = new int[numCourses];
        Queue<Integer> qSet = new LinkedList<Integer>();
        List<Integer>[] graph = new List[numCourses];
        for(int i = 0; i < prerequisites.length; i++) {
            getIndex[prerequisites[i][0]] ++;
            int key = prerequisites[i][1];
            int value = prerequisites[i][0];
            if(graph[key] == null) graph[key] = new ArrayList<Integer>();
            graph[key].add(value);
        }
        for(int i = 0; i < getIndex.length; i++) {
            if(getIndex[i] == 0)
                qSet.offer(i);
        }
        
        while(!qSet.isEmpty()) {
            int tem = qSet.poll();
            result[start++] = tem;
            if(graph[tem] != null) {
                for(int c : graph[tem]) {
                    edges --;
                    if(--getIndex[c] == 0)
                        qSet.offer(c);
                }
            }
        }
        if(edges != 0) return new int[0];
        return result;
    }
}