### 题目

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.
• You may assume that there are no duplicate edges in the input prerequisites.

### 总体思路

1. 计算所有课先导课的数量。
2. 标出所有没有先导课的初级课（他们是第一批“叶节点”）
3. 把所有以这些初级课为先导课的课的先导课数量减去1.
4. 标出新一批先导课数量为0的课程，他们也是证明可以完成的课。
5. 重复3和4步骤。

### 深度优先（DFS）的递归回溯算法

Map先把Edge List收集起来，复杂度 $O(m)$medge的数量。（：用完的edge就删掉，可以优化效果。）

#### 代码

/**
* 用HashMap和HashSet储存图的信息
* 用完就删掉用过的edge
*/
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer,List<Integer>> schedule = new HashMap<>();
for (int[] pair : prerequisites) {
int course = pair[0];
List<Integer> pre = schedule.get(course);
if (pre == null) {
List<Integer> preList = new ArrayList<>();
schedule.put(course,preList);
} else {
}
}
boolean[] canFinish = new boolean[numCourses];
boolean[] waitingList = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
if (!canFinishThisCourse(i,schedule,waitingList,canFinish)) { return false; }
}
return true;
}
public boolean canFinishThisCourse(int course, Map<Integer,List<Integer>> schedule, boolean[] waitingList, boolean[] canFinish) {
if (canFinish[course]) { return true; }
if (waitingList[course]) { return false; }
List<Integer> preList = schedule.get(course);
schedule.remove(course);
if (preList == null) { canFinish[course] = true; return true; }
// dfs backtracking
waitingList[course] = true;
for (int pre : preList) {
if (!canFinishThisCourse(pre,schedule,waitingList,canFinish)) { return false; }
}
waitingList[course] = false;
canFinish[course] = true; return true;
}
}


#### 直接用Edge List

/**
* 尝试直接使用Edge List的图信息
*/
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
boolean[] canFinish = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
if (!canFinishThisCourse(i,prerequisites,new boolean[numCourses],canFinish)) { return false; }
}
return true;
}
public boolean canFinishThisCourse(int course, int[][] prerequisites, boolean[] waitingList, boolean[] canFinish) {
if (canFinish[course]) { return true; }
if (waitingList[course]) { return false; } // find circle
// dfs backtracking
waitingList[course] = true;
for (int[] pair : prerequisites) {
if (pair[0] == course) {
if (!canFinishThisCourse(pair[1],prerequisites,waitingList,canFinish)) { return false; }
}
}
waitingList[course] = false;
canFinish[course] = true;
return true;
}
}


#### 转成Matrix

/**
* 尝试把图信息转换成Matrix的形式。
* 并且waitingList和canFinish也都用数组表示
*/
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
boolean[][] prerequiMatrix = new boolean[numCourses][numCourses];
for (int[] edge : prerequisites) {
prerequiMatrix[edge[0]][edge[1]] = true; // edge[0] require edge[1]
}
boolean[] canFinish = new boolean[numCourses];
boolean[] waitingList = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
if (!canFinishThisCourse(i,prerequiMatrix,waitingList,canFinish)) { return false; }
}
return true;
}
public boolean canFinishThisCourse(int course, boolean[][] prerequiMatrix, boolean[] waitingList, boolean[] canFinish) {
if (canFinish[course]) { return true; }
if (waitingList[course]) { return false; }
// dfs backtracking
waitingList[course] = true;
for (int i = 0; i < prerequiMatrix.length; i++) {
if (prerequiMatrix[course][i]) { // i is the required course
if (!canFinishThisCourse(i,prerequiMatrix,waitingList,canFinish)){ return false; }
}
}
waitingList[course] = false;
canFinish[course] = true;
return true;
}
}


### 广度优先（BFS） Topological Sort法

#### 代码

/**
* Topological Search (BFS)  改进版
* 从叶节点开始，按照深度顺序，一层层梳理
* 改进是：用过的边，马上删掉。可以将search的过程复杂度降到 O(m)。m为edge的数量。
*/
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// reduce edge list by pre & calculate degree
Map<Integer,List<Integer>> edges = new HashMap<>();
int[] degree = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
edges.put(i,new ArrayList<Integer>());
}
for (int[] edge : prerequisites) {
degree[edge[0]]++;
}
// Topological Search
for (int i = 0; i < numCourses; i++) {
if (degree[i] == 0) { zeroDegree.offer(i); }
}
while (!zeroDegree.isEmpty()) {
int course = zeroDegree.poll();
List<Integer> children = edges.remove(new Integer(course));
for (int child : children) {
if (--degree[child] == 0) { zeroDegree.offer(child); }
}
degree[course] = -1;
}
for (int i = 0; i < numCourses; i++) {
if (degree[i] > 0) { return false; }
}
return true;
}
}