How do I know if the Course Schedule problem has a cycle?

By building the adjacency list and tracking indegrees, if any course remains with non-zero indegree after processing, a cycle exists and prevents completion.

Can I solve Course Schedule without a queue?

Yes, a depth-first search can also detect cycles, but the queue-based topological sort using indegree is more intuitive and directly shows available courses.

What is the main failure mode in Course Schedule?

The schedule fails only when a cycle exists in the prerequisite graph, preventing one or more courses from ever becoming available for completion.

How do I efficiently track dependencies between courses?

Use an adjacency list to represent the graph and an indegree array to track how many prerequisites each course has, updating these values during traversal.

What happens if numCourses is large but prerequisites are few?

The algorithm still runs efficiently because it only processes edges and nodes with relevant dependencies, maintaining O(V + E) time and space complexity even with sparse graphs.

#207

Medium

auto_awesome图·搜索

LeetCode 题解工作台

课程表

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

图拓扑排序广度优先搜索队列

题目描述

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

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

例如，先修课程对 [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 <= a_i, b_i < numCourses
prerequisites[i] 中的所有课程对 互不相同

lightbulb

解题思路

方法一：拓扑排序

对于本题，我们可以将课程看作图中的节点，先修课程看作图中的边，那么我们可以将本题转化为判断有向图中是否存在环。

具体地，我们可以使用拓扑排序的思想，对于每个入度为 $0$ 的节点，我们将其出度的节点的入度减 $1$ ，直到所有节点都被遍历到。

如果所有节点都被遍历到，说明图中不存在环，那么我们就可以完成所有课程的学习；否则，我们就无法完成所有课程的学习。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(n + m)$ 。其中 $n$ 和 $m$ 分别为课程数和先修课程数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        g = [[] for _ in range(numCourses)]
        indeg = [0] * numCourses
        for a, b in prerequisites:
            g[b].append(a)
            indeg[a] += 1
        q = [i for i, x in enumerate(indeg) if x == 0]
        for i in q:
            numCourses -= 1
            for j in g[i]:
                indeg[j] -= 1
                if indeg[j] == 0:
                    q.append(j)
        return numCourses == 0

speed

复杂度分析

指标	值
时间	O(V + E)
空间	O(V + E)

psychology

面试官常问的追问

外企场景

question_mark
Do you handle cases where the graph contains cycles preventing course completion?
question_mark
Can you implement the topological ordering using indegree tracking and a queue efficiently?
question_mark
Will you verify that every course reaches zero indegree after processing to confirm completion?

warning

常见陷阱

外企场景

error
Forgetting to initialize the indegree array correctly, which can lead to missing courses that should start with zero indegree.
error
Modifying the queue or indegree counts incorrectly, causing false detection of cycles or skipping courses that should be processed.
error
Assuming that courses with zero prerequisites at the start always guarantee completion without checking the entire graph for hidden cycles.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return a valid ordering of courses if possible, not just a boolean indicating completion.
arrow_right_alt
Determine the minimum number of semesters needed to finish all courses given that multiple courses can be taken simultaneously if prerequisites allow.
arrow_right_alt
Handle a dynamic list of prerequisites where courses can be added or removed, and check completion feasibility incrementally.

help

常见问题

外企场景

继续练习

#206 反转链表 #1 两数之和