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

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List[] graph = new ArrayList[numCourses];
    for (int i = 0; i < numCourses; i++) {
        graph[i] = new ArrayList<Integer>();
    }
    for (int[] pair : prerequisites) {
        graph[pair[1]].add(pair[0]);
    }
    boolean[] onpath = new boolean[numCourses];
    boolean[] visited = new boolean[numCourses];
    for (int i = 0; i < numCourses; i++) {
        if (!visited[i] && !dfs(graph, i, visited, onpath)) {
            return false;
        }
    }
    return true;
}

private boolean dfs(List[] graph, int course, boolean[] visited, boolean[] onpath) {
    onpath[course] = true;
    for (int i = 0; i < graph[course].size(); i++) {
        int neighbor = (int)graph[course].get(i);
        if (onpath[neighbor] || !dfs(graph, neighbor, visited, onpath)) {
            return false;
        }
    }
    visited[course] = true;
    onpath[course] = false;
    return true;
}

Course Schedule II

public int[] findOrder(int numCourses, int[][] prerequisites) {
    int[] indegrees = new int[numCourses];
    List[] graph = new ArrayList[numCourses];
    for (int[] pair : prerequisites) {
        indegrees[pair[0]]++;
        if (graph[pair[1]] == null) {
            graph[pair[1]] = new ArrayList<Integer>();
        }
        graph[pair[1]].add(pair[0]);
    }
    Deque<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegrees[i] == 0) queue.add(i);
    }
    int select = 0;
    int[] res = new int[numCourses];
    while (!queue.isEmpty()) {
        int cur = queue.pollFirst();
        res[select] = cur;
        select += 1;
        if (graph[cur] != null) {
            for (int i = 0; i < graph[cur].size(); i++) {
                int neighbor = (int)graph[cur].get(i);
                indegrees[neighbor]--;
                if (indegrees[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }
    }
    return select == numCourses ? res : new int[0];
}