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)]
# 構(gòu)造入度表和拓?fù)? for cur, pre in prerequisites:
indegrees[cur] += 1
adjacency[pre].append(cur)
# 構(gòu)造 0 入度隊(duì)列
queue = deque()
for i in range(numCourses):
if indegrees[i] == 0: queue.append(i)
# BFS 拓?fù)渑判? 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 注意事項(xiàng)
暫無(wú)
