本文最后更新于 390 天前，其中的信息可能已经有所发展或是发生改变。
题目描述：
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
提示：
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesprerequisites[i]中的所有课程对 互不相同
解法一：拓扑排序
算法思路：
题意理解：
- 一共有
n门课要上，编号为0 ~ n-1。 - 先决条件
[1, 0]，表示要上课1，必须先上完课0。 - 给你
n和一个先决条件表，请你分析是否能完成所有课程。
举例分析：
假设有 n = 6，先决条件表：[[3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4]]
我们可以用有向图来表示课程之间的依赖关系：
上图叫有向无环图，把一个 有向无环图 转变成 线性的排序 叫做拓扑排序。
- 初始时，课程 0、1、2 没有前置课程，节点的入度为 0，课程 3、4、5 分别有两门前置课程，节点入度为 2。
- 每次选择课程时，只能选择没有前置课程的，也就是入度为
0的。 - 在上面的例子中：
- 先选择 0，课 3 的前置课程少了一门，入度由 2 变成 1。
- 接着选 1，课 3 的入度变为 0，课 4 的入度变为 1。
- 接着选 2，课 4 的入度变为 0。
- 接着可以依次选择课 3 和课 4，直到选择不到入度为 0 的课程为止。
- 当选择不到入度为0的课程后，如果还有课程入度不为 0，那么不能完成所有的课程，反之，则可以学完所有课程。
代码实现：
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] inDegree = new int[numCourses]; // 入度数组
HashMap<Integer, List<Integer>> map = new HashMap<>(); // 邻接表
// 构建入度数组和邻接表
for (int i = 0; i < prerequisites.length; i++) {
inDegree[prerequisites[i][0]]++; // 求课的初始入度值
if (map.containsKey(prerequisites[i][1])) { // 当前课已经存在于邻接表
map.get(prerequisites[i][1]).add(prerequisites[i][0]); // 添加依赖它的后续课
} else { // 当前课不存在于邻接表
List<Integer> list = new ArrayList<>();
list.add(prerequisites[i][0]);
map.put(prerequisites[i][1], list);
}
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < inDegree.length; i++) { // 所有入度为0的课入列
if (inDegree[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
int selected = queue.poll(); // 当前选的课，出列
List<Integer> toEnQueue = map.get(selected); // 获取这门课对应的后续课
if (toEnQueue != null && !toEnQueue.isEmpty()) { // 确实有后续课
for (int i = 0; i < toEnQueue.size(); i++) {
int dependentCourse = toEnQueue.get(i);
inDegree[dependentCourse]--; // 依赖它的后续课的入度-1
if (inDegree[dependentCourse] == 0) { // 如果因此减为0，入列
queue.offer(dependentCourse);
}
}
}
}
return count == numCourses; // 选了的课等于总课数，true，否则false
}
}
复杂度分析：
时间复杂度： O(n + m)
空间复杂度： O(n + m)
