0X00 模板
直接拿 207 的题解吧
from collections import deque
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] += 1
adjacency[pre].append(cur)
# 构造 0 入度队列
queue = deque()
for i in range(numCourses):
if indegrees[i] == 0: queue.append(i)
# BFS 拓扑排序
while queue:
pre = queue.popleft()
numCourses -= 1
# pre 后面的都减一
for follow in adjacency[pre]:
indegrees[follow] -= 1
if not indegrees[follow]: queue.append(follow)
return not numCourses
0X01 注意事项
暂无
网友评论