[LeetCode]207. 课程表(Course Schedule)

题目描述

现在你总共有 n 门课需要选,记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件,判断是否可能完成所有课程的学习?

示例 1:

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

示例 2:

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

说明:

  1. 输入的先决条件是由边缘列表表示的图形,而不是邻接矩阵。详情请参见图的表示法。
  2. 你可以假定输入的先决条件中没有重复的边。

提示:

  1. 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环,则不存在拓扑排序,因此不可能选取所有课程进行学习。
  2. 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程(21分钟),介绍拓扑排序的基本概念。
  3. 拓扑排序也可以通过 BFS 完成。

解题思路

  1. 方法一:拓扑排序(Kahn 算法)。
    1. 遍历生成两个数据结构:degree 用来存储该节点的前驱节点数目,即该节点依赖的节点数目;adjacency 是邻接表,用来存储该节点的后继节点,即依赖于该节点的节点。
    2. 将所有 degree 为 0 的节点入队。
    3. 只要队列非空,就出队,将该节点放入结果中,对其后继节点 degree 减一,对所有 degree 为 0 的后继节点入队。
    4. 当队列为空时,检查结果中的节点数目,若相等,则说明没有环。
  2. 方法二:深度优先搜索(DFS)。将原始的布尔 visited 变量更改为拥有三个状态,表示是否正在被搜索中,若遇到第三种状态,则说明有环。

代码

Python 3.6

方法一:拓扑排序(Kahn 算法)

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
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
if numCourses < 2:
return True
degree = {} # 度。表示该节点之前还有几个依赖的节点
adjacency = {} # 邻接表。存储该节点的后继节点
for i in range(numCourses):
degree[i] = 0
for ref in prerequisites:
adjacency.setdefault(ref[1], []).append(ref[0]) # 存储依赖关系
degree[ref[0]] += 1
queue = []
for i in range(numCourses):
if degree[i] == 0:
queue.append(i)
degree[i] = -1
res = []
while queue:
node = queue.pop(0)
res.append(node)
if node not in adjacency:
continue
for i in adjacency[node]:
degree[i] -= 1
if degree[i] == 0:
queue.append(i)
degree[i] = -1
return len(res) == numCourses

执行用时:140 ms
内存消耗:15 MB

方法二:深度优先搜索(DFS)

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
31
32
33
34
35
36
37
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
length = len(prerequisites)
if length == 0:
# 若没有要学习的课程,则肯定可以学完
return True

# visited 有三个状态:
# 0: 没有被遍历过;
# 1: 已经被遍历过;
# 2: 正在被遍历,如果深度优先搜索时碰到了状态2,说明存在环
visited = [0] * numCourses

inverse_course = [set() for _ in range(numCourses)] # 逆邻接表,用来存储学习某课程之前需要先完成的课
for second, first in prerequisites:
inverse_course[second].add(first)

for i in range(numCourses):
# 对于n门课,若发现有环,则说明学不完,退出
if self.dfs(i, inverse_course, visited):
return False
return True

def dfs(self, idx, inverse_course, visited):
# 该函数返回是否有环
if visited[idx] == 2:
return True
if visited[idx] == 1:
return False
visited[idx] = 2 # 把当前遍历的节点设置为正在DFS
for course in inverse_course[idx]:
# 遍历当前节点之前需要学习的节点,若有环,则直接返回
if self.dfs(course, inverse_course, visited):
return True

visited[idx] = 1 # 遍历完成后将当前节点设置为已经遍历过
return False

执行用时:152 ms
内存消耗:16.8 MB

参考

https://leetcode-cn.com/problems/course-schedule/solution/tuo-bu-pai-xu-by-liweiwei1419