LeetCode 207. 课程表

题目

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
  请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

例：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

方法：拓扑排序

• inDegree 存储每门课的入度，初始化为零； relationDict 以字典的形式记录每门课的后续课程，key 表示课程，value 表示该课程的后续课程，用 list 表示
• 循环遍历 prerequisites
  • 计算每门课的入度
  • 记录课与课间的关系
• queue 为双向队列，存储当前入度为零的课程
• 循环遍历 inDegree，将入度为零的课程放入队列 queue
• 循环直至队列为空
  • current 存储当前课程，通过将双向队列的最左输出得到
  • 选修当前课程 current，那么选修课程数量 numCourses 减一
  • 获取当前选修课程 current 的关系，即该课程的后继课程
  • 若存在后继课程，那么将其所有的后继课程的入度减一，并判断此时的入度是否为零，若为零，表示该课程已可以被选修，将其加入队列 queue
• 若所有课程已被选修，即 numCourses 为零，那么返回 True；否则，返回 False

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        from collections import deque

        inDegree = [0] * numCourses
        relationDict = collections.defaultdict(list)

        for course in prerequisites:
            inDegree[course[0]] += 1
            relationDict[course[1]].append(course[0])
        
        queue = deque()
        for i in range(len(inDegree)):
            if inDegree[i] == 0:
                queue.append(i)
        
        while queue:
            current = queue.popleft()
            numCourses -= 1
            relation = relationDict[current]
            if relation:
                for course in relation:
                    inDegree[course] -= 1
                    if inDegree[course] == 0:
                        queue.append(course)
        
        return numCourses == 0

相关知识

• 双向队列： collections.deque()
  

参考

代码相关：https://leetcode.cn/problems/course-schedule/solution/bao-mu-shi-ti-jie-shou-ba-shou-da-tong-tuo-bu-pai-/
deque：https://www.cnblogs.com/ranzhong/p/12438841.html