题目描述

[EN | CN]

你这个学期必须选修 numCourse 门课程,记为 0 到 numCourse - 1

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

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

示例 1:

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

示例 2:

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

提示:

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

解法 1:DFS

要想完成所有课程的学习,其实只要这些课程没有循环依赖就可以。

所以我们可以先遍历一遍邻接表,用一个字典 src_to_dst 存一下每个结点的邻接结点,构成邻接表。然后我们从每一个结点出发做 DFS,找所有路径走到底是不是会形成环即可。这里要注意:搜过的结点不需要再搜(剪枝),可以用一个 detected 集合保存搜过的结点。

复杂度分析略。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        src_to_dst = {src:set() for src in range(numCourses)}
        for src, dst in prerequisites:
            src_to_dst[src].add(dst)

        detected = set()
        def detect(passed):
            curr = passed[-1]
            for dst in src_to_dst[curr]:
                if dst in passed:
                    return False
                if dst in detected:
                    continue
                if detect(passed + [dst]) == False:
                    return False
            detected.add(curr)
            return True

        for src in range(numCourses):
            if src not in detected and detect([src]) == False:
                return False

        return True
  • 执行用时:112 ms, 在所有 Python3 提交中击败了 39.54% 的用户。
  • 内存消耗:32.4 MB, 在所有 Python3 提交中击败了 5.38% 的用户。

解法 2:拓扑排序

拓扑排序(Topological Sort)指的是对 有向无环图 的顶点进行线性排序,使得对于从顶点 $u$ 到顶点 $v$ 的每个有向边,$u$ 在排序中都在 $v$ 之前。当且仅当图中没有环时,才存在合法的拓扑排序。因此我们可以尝试对一个图进行拓扑排序,如果无法构建合法的拓扑排序,则说明图中存在环。

在本题中,其具体做法为:

  1. 遍历所有边,用一个字典 src_to_dst 保存每个结点的邻接结点,dst_to_indegree 保存每个结点的入度(指向该结点的结点数)。
  2. 循环进行以下操作:
    • 找出 入度(即指向该结点的结点数量)为 0 的结点 node,存到数组 rets 中,表示该结点已经「完结」,即指向该结点的路径可以结束,不会形成环。
    • 更新 dst_to_indegree,将 node 结点指向的每一个 dst 的入度减一。
    • 移除 dst_to_indegree 中的 node 结点。
  3. 当已经没有入度为 0 的结点时,检查 rets 的结点数量是否与总结点数量一致,一致则说明所有路径都可以结束;否则说明存在图中存在环,导致环中的结点的入度全都 > 0。

复杂度分析略。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        src_to_dsts = {src:set() for src in range(numCourses)}
        dst_to_indegree = {dst:0 for dst in range(numCourses)}
        for src, dst in prerequisites:
            src_to_dsts[src].add(dst)
            dst_to_indegree[dst] += 1

        rets = set()
        while True:
            dsts_without_src = {dst for dst, indegree in dst_to_indegree.items() if indegree == 0}
            if len(dsts_without_src) == 0:
                break
            for node in dsts_without_src:
                rets.add(node)
                for dst in src_to_dsts[node]:
                    dst_to_indegree[dst] -= 1
                dst_to_indegree.pop(node)

        return len(rets) == numCourses
  • 执行用时:140 ms,在所有 Python3 提交中击败了 26.50% 的用户。
  • 内存消耗:14.6 MB,在所有 Python3 提交中击败了 45.16% 的用户。