There are a total of
numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a<sub>i</sub>, b<sub>i</sub>] indicates that you must take course b<sub>i</sub> first if you want to take course a<sub>i</sub>.For example, the pair
[0, 1], indicates that to take course 0 you have to first take course 1.Return
true if you can finish all courses. Otherwise, return false.Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: 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.
Constraints:
1 <= numCourses <= 10<sup>5</sup>0 <= prerequisites.length <= 5000
prerequisites[i].length == 20 <= a<sub>i</sub>, b<sub>i</sub> < numCourses
All the pairs prerequisites[i] are unique.题目大意：
课程有先修课要求，求是否可以完成所有课程
解题思路：
跟LeetCode 210 Course Schedule II几乎一样，此题求可否完成，那题求课程顺序。区别在于return那一句返回bool还是res
解题步骤：
N/A
注意事项：
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
in_degree = [0] * numCourses
graph = [[] for _ in range(numCourses)]
for li in prerequisites:
in_degree[li[0]] += 1
graph[li[1]].append(li[0])
queue = collections.deque([i for i in range(len(in_degree)) if in_degree[i] == 0])
res = []
while queue:
node = queue.popleft()
res.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return numCourses == len(res)
算法分析：
时间复杂度为O(n)，空间复杂度O(n)
