207. 课程表

题目-中等难度

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

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

示例

示例 1：

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

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i] 中的所有课程对 互不相同

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/summary-ranges
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1. bfs

时间
52ms
击败 55.73%使用 Python3 的用户
内存
16.81MB
击败 72.88%使用 Python3 的用户

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 初始化需要学习的课程列表
        deg = [0] * numCourses
        # 初始化字典用于存储先决课表, 键为先决课程, 值为先决完成后可学的课程列表
        dic = defaultdict(list)
        # 添加课程ai到deg, 在字典中添加课程ai到先决课程bi
        for ai,bi in prerequisites:
            deg[ai] += 1
            dic[bi].append(ai)
        # 创建列表, 存储为deg中值为0的课程(可直接完成的课程)
        li = [i for i,j in enumerate(deg) if j == 0]
        # 记录已访问的课程数量
        visited = 0
        # 当列表仍然存在为0的课程, 继续遍历
        while li:
            # 访问课程数量+1, 因为li每次遍历只获取1个课程
            visited+=1
            # 获取列表中做左侧课程
            a = li.pop(0)
            # 遍历当前必修课程研习后, 可以学习的课程
            for i in dic[a]:
                # 匹配一个先决课程
                deg[i] -= 1
                # 列表放入下一个课程，继续遍历匹配下一个先觉课程
                if deg[i] == 0:
                    li.append(i)
        # 当所有课程被遍历到, 则满足条件
        return numCourses == visited

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30