Course Schedule
有 numCourses 门课，编号从 0 到 numCourses-1。prerequisites 中的每一对 [a, b] 都表示你必须先完成课程 b，才能开始课程 a。如果存在某种顺序，让你完成所有课程，就返回 true；如果不存在，就返回 false。
函数
- numCoursesinteger
- 课程数量
- prerequisitesinteger-2d-array
- 每一对 [a, b] 都表示课程 b 在课程 a 之前
- 返回值boolean
- 如果每门课程都能完成，则为 true，否则为 false。
约束条件
1 ≤ numCourses ≤ 1051 ≤ prerequisites.length ≤ 5000- 每对
[a, b]都满足0 ≤ a, b < numCourses。 - 不会有重复出现的配对。
- 一对可能会把同一门课程写两次，
[a, a]。这门课程需要先修它自己，因此永远无法选修。
示例
- 输入
- numCourses = 4prerequisites = [[1, 0], [2, 1], [3, 1]]
- 输出
- true
- 解释
- 课程 0 没有先修课程，所以你先修它。这样课程 1 就可以开始了，而课程 1 又为课程 2 和 3 腾出了空间，因此按 0、1、2、3 的顺序修课可行。
- 输入
- numCourses = 3prerequisites = [[0, 2], [2, 1], [1, 0]]
- 输出
- false
- 解释
- 课程 0 等待 2，2 等待 1，1 等待 0。它们三个互相等待，形成了一个循环，所以谁都无法先开始。
进阶
一个学期可以安排任意数量的课程，只要每门课的先修课程都已在更早的学期完成。修完所有课程最少需要几个学期？
提示
逐个打开提示，每个都会多透露一点。
把每门课程画成一个点，并把每对
[a, b]画成一支从b指向a的箭头。这样的图中出现什么形状会让你无法完成课程？一个由箭头组成的循环。循环中的每门课程都在等待同一循环中的另一门课程，因此没有一门课程能先开始。问题是，这个图中是否存在环。
统计每门课还需要等待多少门先修课。从计数为 0 的课程开始建立队列，每次取出一门课程时，就将所有等待它的课程的计数减 1。如果最终进入队列的课程少于
numCourses门，就说明存在循环。
题解
对于每一对 [a, b]，画一支从 b 指向 a 的箭头。只有当这个图没有环时，才能完成所有课程；该图有 V = numCourses 个节点和 E = prerequisites.length 支箭头。Kahn 算法会像学生规划课程那样检查：不断学习先修课程已完成的课程，看看是否能学完所有课程。
一轮接一轮地学习每门免费课程
结果正确，但无法在最大的测试中运行完毕
思路
每一轮都选出所有尚未选修且先修课程都已修完的课程。当某一轮没有选修任何课程时就停止，如果所有课程都已修完，则返回 true。只有当每门剩余课程都在等待另一门剩余课程时，这一轮才会没有选修任何课程，这就形成了一个循环。
每一轮都会重新检查每一对关系和每门课程，但可能只选修一门课程。在 100,000 门课程中有一条包含 5,001 门课程的链时，需要超过 5,000 轮：约 5 × 10^8 次检查。
算法
- 将每门课程标记为未修。
- 如果某一对课程中，有一门课程是该课程尚未修读的先修课，则将该课程标记为受阻。
- 修读所有既未修读也未受阻的课程。
- 如果这一轮没有修读任何课程，就停止；否则返回第 2 步。
- 如果所有课程都已修读，则返回 true。
def canFinish(numCourses, prerequisites):
taken = [False] * numCourses
count = 0
while True:
# A course is blocked while one of its prerequisites is not taken.
blocked = [False] * numCourses
for course, before in prerequisites:
if not taken[before]:
blocked[course] = True
# Take every course that is free this round.
progress = False
for c in range(numCourses):
if not taken[c] and not blocked[c]:
taken[c] = True
count += 1
progress = True
if not progress:
break
return count == numCourses使用三种状态的深度优先搜索
思路
深度优先搜索通过跟踪遍历路径来查找环。给每门课设置三种状态：未访问、在路径上、已完成。从一门课沿箭头前往依赖它的课程。进入一门课时，将其标记为在路径上；当它的所有箭头都探索完后，将其标记为已完成。
如果箭头指向路径上的课程，就形成了一个环：返回 false。如果箭头指向已完成的课程，则是安全的，因为从该课程可到达的所有课程都已检查过，且不存在环，所以一门课程被再次访问本身并不构成环。每门课程只进入一次，每条箭头只跟随一次：O(V + E)。
算法
- 为每门课程构建等待它的课程列表。
- 对于每门尚未访问的课程，将它标记为在路径上，并将它压入栈中。
- 查看栈顶。如果它没有剩余箭头，就将它标记为已完成并将它弹出；否则，沿着它的下一个箭头前进。
- 如果箭头指向路径上的课程，就返回 false。如果它指向尚未访问的课程，就将该课程标记为在路径上，并将它压入栈中。
- 所有课程都完成后，返回 true。
def canFinish(numCourses, prerequisites):
unlocks = [[] for _ in range(numCourses)]
for course, before in prerequisites:
unlocks[before].append(course)
# 0 = not visited, 1 = on the current path, 2 = done, no cycle below it
state = [0] * numCourses
# next_edge[c] counts the edges out of c the search has already followed.
next_edge = [0] * numCourses
for start in range(numCourses):
if state[start] != 0:
continue
# A stack of our own instead of recursion: a chain of 5,000
# courses would go 5,000 calls deep.
state[start] = 1
stack = [start]
while stack:
course = stack[-1]
if next_edge[course] == len(unlocks[course]):
state[course] = 2
stack.pop()
continue
nxt = unlocks[course][next_edge[course]]
next_edge[course] += 1
if state[nxt] == 1:
return False # an edge back to the current path closes a cycle
if state[nxt] == 0:
state[nxt] = 1
stack.append(nxt)
return TrueKahn 算法
思路
一门课会在某个时刻变得可以免费修读：也就是它的最后一门先修课被修读之后。因此，记录每门课的入度，也就是它还需要等待的先修课数量，并将所有计数为 0 的课程放入队列。修读一门课会让每门等待它的课程的计数减 1，计数降到 0 的课程就会加入队列。在第一个示例中，计数从 0、1、1、1 开始：修读 0 后，1 就可以修读；修读 1 后，2 和 3 就可以修读。每门课只会进入队列一次，每条边也只会让一个计数减 1 次：O(V + E)。
如果队列为空时课程 a 还未修读，它的计数就大于 0，因此 a 的某门先修课也尚未修读，依此类推。沿着这条路径一定会再次遇到某门课程：这就形成了一个环。反过来，环上的每门课程都在等待环上的另一门课程，因此没有一门能先修读。课程离开队列的顺序就是一个有效的安排。
算法
- 对于每一对 [a, b]，将 a 添加到等待 b 的课程列表中，并将 a 的入度加 1。
- 将所有入度为 0 的课程放入队列。
- 从队列中取出一门课程并计数。将所有等待它的课程的入度减 1，并将每个入度变为 0 的课程加入队列。
- 队列为空时，返回计数是否等于
numCourses。
from collections import deque
def canFinish(numCourses, prerequisites):
# unlocks[b] lists the courses that wait for b.
# indegree[a] counts the prerequisites of a that are not taken yet.
unlocks = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for course, before in prerequisites:
unlocks[before].append(course)
indegree[course] += 1
# Every course with no prerequisites can be taken right away.
queue = deque(c for c in range(numCourses) if indegree[c] == 0)
taken = 0
while queue:
course = queue.popleft()
taken += 1
for nxt in unlocks[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
# A course on a cycle never gets down to 0, so it is never taken.
return taken == numCourses
易错点和边界情况
- 把方向弄反。
[a, b]表示 b 先修：箭头从 b 指向 a，a 的入度加 1。 - 忘记那些没有出现在任何课程对中的课程。对于
numCourses = 5和唯一的课程对[4, 3]，课程 0、1 和 2 也必须一开始就在队列中。 - 深度优先搜索中只用了两种状态，而不是三种。在菱形结构 0 → 1、0 → 2、1 → 3、2 → 3 中，课程 3 会被访问两次，如果你只记录“已访问”，就会误以为存在循环。
- 对一条包含 5,000 门课程的链递归：递归深度达到 5,000 层，超过 Python 默认的 1,000 层限制。
- 队列为空时，没有检查是否已修完
numCourses门课程就返回 true。第二个示例会返回 true。
常见问题3
课程安排问题的时间复杂度是多少？
时间复杂度为 O(V + E)，其中 V 是课程数，E 是课程对数，可使用 Kahn 算法或深度优先搜索。每个课程对都会读取一次，每门课程都会处理一次。列表和计数所需的空间复杂度为 O(V + E)。
课程安排应该使用 BFS 还是 DFS？
两者的运行时间都是 O(V + E)。Kahn 算法，也就是广度优先版本，不用担心递归深度问题，而且能给出有效的课程顺序。如果还需要报告循环，使用带有三种状态的深度优先搜索是自然的选择，因为栈中的课程就构成了这个循环。
什么是拓扑排序？
有向图中节点的一种排列，其中每条箭头都指向后方；在这里，排列中的每项先修课程都排在需要它的课程之前。当且仅当图中没有环时，这种排列才存在，而 Kahn 算法选取课程的顺序就是其中一种。Course Schedule 要求判断这种排列是否存在。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def canFinish(numCourses, prerequisites):
# 在这里编写代码测试 #1
测试 #2
参数
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
预期输出
true