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

标题

思绪

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

1. class Solution:
2.     def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
3.             # 存储每个点的入度
4.         indegrees = [0 for _ in range(numCourses)]
5.         # 存储邻接关系
6.         adjacency = [[] for _ in range(numCourses)]
8.                 # 统计每个点的入度和邻接关系
9.         for cur, pre in prerequisites:
10.             indegrees[cur] += 1
11.             adjacency[pre] = cur
12.         
13.         # 寻找入度为0的点，作为起始点
14.         que = collections.deque()
15.         for i in range(numCourses):
16.             if not indegrees:
17.                 que.append(i)
18.         
19.         # 当队列中存在入度为0的点时候，就进行遍历
20.         while que:
21.                 # 取出一个点遍历
22.             pre = que.popleft()
23.             numCourses -= 1
24.             # 该点邻接的点的入度减去1
25.             for cur in adjacency[pre]:               
26.                 indegrees[cur] -= 1
27.                 # 当入度为0时候，作为下一个被遍历的点
28.                 if not indegrees[cur]:
29.                     que.append(cur)
30.         
31.         # 当所有点都入度为0时候，则满足拓扑排序
32.         return not numCourses

复制代码