How do I solve the 'Course Schedule II' problem using topological sort?

To solve 'Course Schedule II', use topological sorting with either DFS or BFS. The goal is to find a valid course order by detecting cycles in the graph.

Can I use DFS or BFS for solving 'Course Schedule II'?

Yes, both DFS and BFS are viable approaches. DFS allows for cycle detection via recursive calls, while BFS (Kahn's Algorithm) handles cycle detection using in-degree tracking.

What happens if there is no valid course order in 'Course Schedule II'?

If a cycle exists in the graph, no valid topological order exists. In such cases, you should return an empty array.

How do I handle a case where there are no prerequisites in 'Course Schedule II'?

If there are no prerequisites, the order is trivial, and you can return any order of courses, such as [0, 1, 2, ..., numCourses-1].

What is the time complexity for solving 'Course Schedule II'?

The time complexity for both DFS and BFS approaches is O(V + E), where V is the number of courses and E is the number of prerequisites.

#210

Medium

auto_awesome图·搜索

LeetCode 题解工作台

课程表 II

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1 。给你一个数组 prerequisites ，其中 prerequisites[i] = [a i , b i ] ，表示在选修课程 a i 前必须先选修 b i 。例如，想要学习课程 0 ，你需要先完…

深度优先搜索广度优先搜索图拓扑排序

题目描述

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [a_i, b_i] ，表示在选修课程 a_i 前必须先选修 b_i 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

示例 3：

输入：numCourses = 1, prerequisites = []
输出：[0]

提示：

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
a_i != b_i
所有[a_i, b_i] 互不相同

lightbulb

解题思路

方法一：拓扑排序

我们创建一个邻接表 $g$ ，用于存储每个节点的后继节点，同时还需要一个数组 $indeg$ 存储每个节点的入度。在构建邻接表的同时，我们也统计每个节点的入度。当入度为 $0$ 的节点代表没有任何前置课程，可以直接学习，我们将其加入队列 $q$ 中。

当队列 $q$ 不为空的时候，我们取出队首的节点 $i$ ：

我们将 $i$ 放入答案中；
接下来，我们将 $i$ 的所有后继节点的入度减少 $1$ 。如果发现某个后继节点 $j$ 的入度变为 $0$ ，则将 $j$ 放入队列 $q$ 中。

在广度优先搜索的结束时，如果答案中包含了这 $n$ 个节点，那么我们就找到了一种拓扑排序，否则说明图中存在环，也就不存在拓扑排序了。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(n + m)$ 。其中 $n$ 和 $m$ 分别是节点数和边数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        g = defaultdict(list)
        indeg = [0] * numCourses
        for a, b in prerequisites:
            g[b].append(a)
            indeg[a] += 1
        ans = []
        q = deque(i for i, x in enumerate(indeg) if x == 0)
        while q:
            i = q.popleft()
            ans.append(i)
            for j in g[i]:
                indeg[j] -= 1
                if indeg[j] == 0:
                    q.append(j)
        return ans if len(ans) == numCourses else []

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Understanding of graph traversal methods like DFS and BFS.
question_mark
Ability to detect cycles in a directed graph.
question_mark
Knowledge of topological sorting and its application in real-world scheduling problems.

warning

常见陷阱

外企场景

error
Forgetting to check for cycles in the graph, which can lead to incorrect results.
error
Not handling the case where there are no prerequisites (empty prerequisite list).
error
Incorrectly assuming there is always one valid topological order, when multiple orders are possible.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Course Schedule III, where you are given a limited number of semesters to complete the courses.
arrow_right_alt
Course Schedule IV, where some courses are optional, and you're tasked with finding the minimum set of courses to complete all prerequisites.
arrow_right_alt
Course Schedule V, where the graph may contain additional constraints such as course dependencies that vary over time.

help

常见问题

外企场景

继续练习

#207 课程表 #310 最小高度树 #329 矩阵中的最长递增路径