207. 课程表
前言
「力扣题解」系列致力于分享有价值的题目、探讨更优秀的解法。
这是本系列的第 5 篇题解，更多题解关注 Somnia1337@力扣。
离散数学中学习了拓扑排序，本篇讲解其在实际问题中的应用。
题目描述
难度：🟡中等
你必须选修 numCourses 门课程，记为 0 到 numCourses - 1。
在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi]，表示如果要学习课程 ai 则必须先学习课程 bi。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你判断是否可能完成所有课程的学习？如果可以，返回 true；否则，返回 false。
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。这是可能的。输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。题意理解 & 解题思路
本题题解区有一篇高质量题解，我的水平不足以讲解得如此清晰，故直接搬运并小改如下：
作者：笨猪爆破组
链接：https://leetcode.cn/problems/course-schedule/
题意理解
一共有 n 门课，编号为 0 ~ n-1。
先决条件 [b, a] 的意思是必须先上课 a、才能上课 b。
给出 n 和一个先决条件表，判断能否完成所有课程。
用有向图描述先后关系
示例：n = 6，先决条件表：[[3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4]]。
课 0, 1, 2 没有先修课，可以直接选，其余的课都有 2 门先修课。
用有向图展现这种依赖关系：
这叫有向无环图，把一个有向无环图转成线性的排序就叫拓扑排序。
有向图的入度和出度：有向边 A B，给 A 增加了 1 个出度，给 B 增加了 1 个入度。
所以，节点 0、1、2 的入度为 0，节点 3、4、5 的入度为 2。
每次选当前可以上的课
每次只能选入度为 0 的课，因为它不依赖别的课，是当前能上的课。选择一门课后，依赖它的下一门课程的入度就减 1。
先选 0，课 3 的先修课就学完了一门，入度由 2 变 1。
再选 1，课 3 的入度变 0，课 4 的入度由 2 变 1。
再选 2，课 4 的入度变 0，现在，课 3、4 的入度为 0，都可以修读了。
持续选择入度为 0 的课，直到全部学完或选不到入度为 0 的课。
BFS
入度为 0 的课是当前能选的，入队。
逐个出队，代表着选择这门课，并将相关课程的入度减 1。
如果相关课的入度更新后变为 0，安排它入队，持续上述过程。
准备工作
每门课的入度需要被记录，以便后续更新。课之间的依赖关系也要记录，这样才知道修读当前课能减小哪些课的入度。
Map<Int, List<Int>>：记录每门课的后续课。int[]：维护每门课的入度。
判断能否修完
用 count 记录出队的课程数，最后判断 count 是否等于总课程数。
复杂度
- 时间复杂度：， 为课程数， 为先决条件表长度
- 空间复杂度：
代码
Java
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// follows: Map, 记录后续课程
// in: int[], 记录入度
Map<Integer, List<Integer>> follows = new HashMap<>();
int[] in = new int[numCourses];
for (int[] edge : prerequisites) {
List<Integer> next = follows.getOrDefault(edge[1], new ArrayList<>());
next.add(edge[0]);
in[edge[0]]++;
follows.put(edge[1], next);
}
// take: Queue, 用于 BFS
Queue<Integer> take = new LinkedList<>();
// 把最初能选的课程入队
for (int i = 0; i < numCourses; i++) {
if (in[i] == 0) take.add(i);
}
// count: int, 记录修读的课程数
int count = 0;
// BFS
while (!take.isEmpty()) {
List<Integer> follow = follows.get(take.poll());
count++;
if (follow == null) continue;
// 更新入度, 为 0 时入队
for (int f : follow) {
in[f]--;
if (in[f] == 0) take.add(f);
}
}
// 修读的课程数是否达到要求
return count == numCourses;
}
}相关题目
210. 课程表 II
630. 课程表 III
最后
更多系列「外源推文」&「生活分享」关注公众号：