简单的tpSort

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        #首先计算每个课程的入度
        #然后列出每个课程的后继
        inDegree=[0]*numCourses
        nextCourses=[[] for _ in range(0,numCourses)]
        for relation in prerequisites:
            afterCourse,beforeCourse=relation[0],relation[1]
            inDegree[afterCourse]+=1
            nextCourses[beforeCourse].append(afterCourse)
        #queue里面放入度为0的课程(不需要先修的课程)
        queue=[]
        for course in range(0,numCourses):
            if inDegree[course]==0:
                queue.append(course)
        count=0
        while queue:
            beforeCourse=queue.pop(0)
            count+=1
            for afterCourse in nextCourses[beforeCourse]:
                inDegree[afterCourse]-=1
                if inDegree[afterCourse]==0:
                    queue.append(afterCourse)
        if count==numCourses:return True
        else:return False

全部评论

相关推荐

不愿透露姓名的神秘牛友
11-19 14:56
点赞 评论 收藏
分享
11-07 16:07
深圳大学 运营
前端飞升:学长,阿里不是卡双非吗,我深也能去吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务