Topological Sort

General Rules:

• 处理依赖关系（Pre-requisties）时，首先计算出每个元素的入度（indegree），其次用一个 Queue 来存储当前入度为0的元素（即无依赖），然后依次去处理各个元素的依赖关系，更新入度，并更新Queue，直到Queue里无元素。

• 处理任务调度（Task Scheduling）。

经典题目

207 Course Schedule 210 Course Schedule II

入度可以看成是每门课依赖于多少门别的课，这样入度为0的课就是无依赖的课，可以直接加进Queue里。随后，将Queue里的元素一个一个取出，此时可以将以该门课为依赖的所有课入度减一，并将新的入度为0的课加进Queue里，直至Queue里无元素。在整个过程中，我们可以计算从Queue里取出了多少个元素，若与numCourses相等，即能完成所有课程。

Course Schedule I --- BFS

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[] indegrees = new int[numCourses];
    for (int[] pair: prerequisites) {
        indegrees[pair[0]]++;
    }
    Deque<Integer> queue = new LinkedList<>();
    for (int i = 0; i < indegrees.length; i++) {
        if (indegrees[i] == 0) {
            queue.add(i);
        }
    }
    int select = 0;
    while (!queue.isEmpty()) {
        int cur = queue.pollFirst();
        select += 1;
        for (int[] pair : prerequisites) {
            if (pair[1] == cur) {
                indegrees[pair[0]]--;
                if (indegrees[pair[0]] == 0) {
                    queue.add(pair[0]);
                }
            }
        }
    }
    return select == numCourses;
}

Course Schedule I --- DFS

Course Schedule II