面试150 课程表

思路

该题等价于判断一个有向图中是否存在环。我们将课程视为图中的节点,先修课[a,b]表示一条从b指向a的有向边（必须先学b才能学a)。然后，我们要用拓扑排序，统计每门课的入度(有多少先学的课程），将所有入度为0的课程加入队列，完成的课程自增，并继续更新后续的入读。如果完成的课程数目等于指定的numcourse，说明无环，课程可以完成，否则说明存在循环依赖，无法完成所有课程。

class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:indegree=[0]*numCoursesgraph=defaultdict(list)for x,y in prerequisites:graph[y].append(x)indegree[x]+=1 #入度自增#建立映射queue=deque([i for i in range(numCourses) if indegree[i]==0])#关键是判断有无环complete=0#入度为0的建立while queue:course=queue.popleft()complete+=1for neighbor in graph[course]:indegree[neighbor]-=1if indegree[neighbor]==0:queue.append(neighbor)return complete==numCourses