210、【图论】课程表（Python）

题目

思路

这道题本质上是一个拓扑排序。每次先统计每个点的入度个数、然后再统计点与点之间的邻接关系，找到入度为0的点作为起始遍历点。之后每遍历到这个点之后，就把这个点后续的邻接关系边的点入度减去一。当某个点入度为0时，继续被加入其中开启下一轮遍历。当遍历完后，如果还有剩余点的话，则说明不满足拓扑要求。

代码实现

class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:# 存储每个点的入度indegrees = [0 for _ in range(numCourses)]# 存储邻接关系adjacency = [[] for _ in range(numCourses)]# 统计每个点的入度和邻接关系for cur, pre in prerequisites:indegrees[cur] += 1adjacency[pre] = cur# 寻找入度为0的点，作为起始点que = collections.deque()for i in range(numCourses):if not indegrees:que.append(i)# 当队列中存在入度为0的点时候，就进行遍历while que:# 取出一个点遍历pre = que.popleft()numCourses -= 1# 该点邻接的点的入度减去1for cur in adjacency[pre]:                indegrees[cur] -= 1# 当入度为0时候，作为下一个被遍历的点if not indegrees[cur]:que.append(cur)# 当所有点都入度为0时候，则满足拓扑排序return not numCourses