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, is it possible for you to finish all courses?
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 it is possible.
2, [[1,0],[0,1]] There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note: The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

時間 O(N) 空間 O(N)

先修課問題本質上是一個有向圖，如果這個圖無環，我們可以根據拓撲排序遍歷到所有節點，如果有環則拓撲排序無法完成，遍歷到的節點將少于總節點數，因為有的節點是孤島。這題我們先根據邊的關系，建一個圖，并計算每個節點的入度，這里用的是數組來建圖。然后從入度為0的節點，也就是入口開始廣度優先搜索，按照拓撲排序的順序遍歷，最后看遍歷過的節點數和總節點數的關系就行了。拓撲排序的使用方法參見外文字典。

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList[] graph = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];
        // 先初始化圖，每個賦一個空列表
        for(int i = 0; i < numCourses; i++){
            graph[i] = new ArrayList();
        }
        // 根據邊建立圖，并計算入度
        for(int i = 0; i < prerequisites.length; i++){
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
            indegree[prerequisites[i][0]]++;
        }
        // 找到有向圖的入口
        Queue queue = new LinkedList();
        for(int i = 0; i < indegree.length; i++){
            if(indegree[i] == 0){
                queue.add(i);
            }
        }
        // 按照拓撲排序的順序，進行廣度優先搜索
        int cnt = 0;
        while(!queue.isEmpty()){
            Integer curr = queue.poll();
            cnt++;
            ArrayList nexts = graph[curr];
            for(int i = 0; i < nexts.size(); i++){
                int next = nexts.get(i);
                indegree[next]--;
                if(indegree[next] == 0){
                    queue.offer(next); 
                }
            }
        }
        return cnt == numCourses;
    }
}

2018/10

func canFinish(numCourses int, prerequisites [][]int) bool {
    graph := make(map[int][]int)
    indegree := make([]int, numCourses)
    // build the graph, count the indegree for each course
    for _, prerequisite := range prerequisites {
        course1 := prerequisite[0]
        course2 := prerequisite[1]
        if graph[course2] != nil {
            graph[course2] = append(graph[course2], course1)
        } else {
            graph[course2] = []int{course1}
        }
        indegree[course1]++
    }
    // find out those with 0 indegree as roots of the graph
    var queue []int
    for i, degree := range indegree {
        if degree == 0 {
            queue = append(queue, i)
        }
    }
    // traverse the graph from each root, decrement the indegree for each leaf
    count := 0
    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]
        count++
        for _, course := range graph[curr] {
            indegree[course]--
            // once a node"s indegree is 0, it becomes a root too
            if indegree[course] == 0 {
                queue = append(queue, course)
            }
        }
    }
    // if all nodes have been the root before, we traversed the entire graph
    return count == numCourses
}

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].

時間 O(N) 空間 O(N)

和I不同的是，這題要返回路徑。其實也沒有什么不同的，不過是多加一個數組，記錄廣度優先搜索的遍歷順序就行了。

當沒有先修課的時候，隨便返回一個順序就行了，所以初始化的時候就初始化為升序序列，方便后面直接返回。

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res = new int[numCourses];
        ArrayList[] graph = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];
        for(int i = 0; i < prerequisites.length; i++){
            if(graph[prerequisites[i][1]] == null){
                graph[prerequisites[i][1]] = new ArrayList();
            }
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
            indegree[prerequisites[i][0]]++;
        }
        Queue queue = new LinkedList();
        for(int i = 0; i < indegree.length; i++){
            if(indegree[i] == 0){
                queue.add(i);
            }
        }
        // 用idx記錄輸出數組的下標
        int idx = 0;
        while(!queue.isEmpty()){
            Integer curr = queue.poll();
            res[idx++] = curr;
            if(graph[curr] == null) continue;
            for(Integer next : graph[curr]){
                if(--indegree[next] == 0){
                    queue.offer(next); 
                }
            }
        }
        // 如果有環則返回空數組
        return idx != numCourses ? new int[0] : res;
    }
}