面试150 课程表Ⅱ

思路

承接前一题课程表的思路,我们在这里只需要多加一个result数组用于存储遍历队列中的课程即可。最后通过判断完成的课程数目与总共的课程数目是否相同来返回result数组，如果有环则返回空数组。

class Solution:def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:graph=defaultdict(list)indegree=[0]*numCoursesresult=[]for x,y in prerequisites:graph[y].append(x)indegree[x]+=1que=deque([i for i in range(numCourses) if indegree[i]==0])complete=0while que:course=que.popleft()complete+=1result.append(course)for neighbor in graph[course]:indegree[neighbor]-=1if  indegree[neighbor]==0:que.append(neighbor)return result if complete==numCourses else []