<div>
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 course0you have to first take course1.
Return true if you can finish all courses. Otherwise, return false.
Example 1:
<pre>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. </pre>
Example 2:
<pre>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. </pre>
Constraints:
1 <= numCourses <= 10<sup>5</sup>0 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= a<sub>i</sub>, b<sub>i</sub> < numCourses- All the pairs prerequisites[i] are unique.
</div>
题目大意：
课程有先修课要求，求是否可以完成所有课程
解题思路：
跟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)
