LeetCode 207: Course Schedule (Topological Sort / Kahn BFS)
LeetCode 207GraphTopological SortBFSToday we solve LeetCode 207 - Course Schedule.
Source: https://leetcode.com/problems/course-schedule/
English
Problem Summary
There are numCourses courses labeled from 0 to numCourses - 1. Each prerequisite pair [a, b] means you must finish b before a. Return whether it is possible to finish all courses.
Key Insight
This is a cycle detection problem on a directed graph. If the prerequisite graph has a cycle, at least one course in that cycle can never have indegree 0, so you cannot finish all courses.
Brute Force and Why Insufficient
Trying all course-taking orders is factorial-time and impossible for constraints. We need linear graph processing.
Optimal Algorithm (Kahn BFS Topological Sort)
1) Build adjacency list b -> a and indegree array.
2) Push all indegree-0 courses into a queue.
3) Pop queue, count processed courses, and decrease indegree of neighbors.
4) If any neighbor indegree becomes 0, push it into queue.
5) After BFS, if processed count equals numCourses, return true; otherwise false.
Complexity Analysis
Time: O(V + E), where V = numCourses and E = prerequisites.length.
Space: O(V + E) for adjacency list, indegree array, and queue.
Common Pitfalls
- Reversing edge direction incorrectly.
- Forgetting to initialize every course node (including isolated ones).
- Counting queue pops incorrectly and misjudging completion.
- Using DFS recursion without robust cycle-state marking, causing false positives/stack issues.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
int[] indegree = new int[numCourses];
for (int[] p : prerequisites) {
int a = p[0], b = p[1];
graph.get(b).add(a);
indegree[a]++;
}
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) q.offer(i);
}
int taken = 0;
while (!q.isEmpty()) {
int cur = q.poll();
taken++;
for (int nxt : graph.get(cur)) {
indegree[nxt]--;
if (indegree[nxt] == 0) q.offer(nxt);
}
}
return taken == numCourses;
}
}func canFinish(numCourses int, prerequisites [][]int) bool {
graph := make([][]int, numCourses)
indegree := make([]int, numCourses)
for _, p := range prerequisites {
a, b := p[0], p[1]
graph[b] = append(graph[b], a)
indegree[a]++
}
queue := make([]int, 0)
for i := 0; i < numCourses; i++ {
if indegree[i] == 0 {
queue = append(queue, i)
}
}
taken := 0
for head := 0; head < len(queue); head++ {
cur := queue[head]
taken++
for _, nxt := range graph[cur] {
indegree[nxt]--
if indegree[nxt] == 0 {
queue = append(queue, nxt)
}
}
}
return taken == numCourses
}class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
vector<int> indegree(numCourses, 0);
for (auto &p : prerequisites) {
int a = p[0], b = p[1];
graph[b].push_back(a);
indegree[a]++;
}
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) q.push(i);
}
int taken = 0;
while (!q.empty()) {
int cur = q.front();
q.pop();
taken++;
for (int nxt : graph[cur]) {
if (--indegree[nxt] == 0) q.push(nxt);
}
}
return taken == numCourses;
}
};from collections import deque
class Solution:
def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
graph = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
indegree[a] += 1
q = deque(i for i in range(numCourses) if indegree[i] == 0)
taken = 0
while q:
cur = q.popleft()
taken += 1
for nxt in graph[cur]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
q.append(nxt)
return taken == numCoursesvar canFinish = function(numCourses, prerequisites) {
const graph = Array.from({ length: numCourses }, () => []);
const indegree = new Array(numCourses).fill(0);
for (const [a, b] of prerequisites) {
graph[b].push(a);
indegree[a]++;
}
const queue = [];
for (let i = 0; i < numCourses; i++) {
if (indegree[i] === 0) queue.push(i);
}
let taken = 0;
for (let head = 0; head < queue.length; head++) {
const cur = queue[head];
taken++;
for (const nxt of graph[cur]) {
indegree[nxt]--;
if (indegree[nxt] === 0) queue.push(nxt);
}
}
return taken === numCourses;
};中文
题目概述
有 numCourses 门课程，编号为 0 到 numCourses - 1。先修关系 [a, b] 表示要先学完 b 才能学 a。请判断是否可以完成所有课程。
核心思路
本质是有向图中的环检测问题。若先修图存在环，则环上的课程都无法把入度降到 0，最终不可能全部修完。
暴力解法与不足
暴力枚举所有选课顺序复杂度接近阶乘，完全不可行。应使用线性时间的图算法。
最优算法（Kahn BFS 拓扑排序）
1）构建邻接表 b -> a 与入度数组。
2）将所有入度为 0 的课程入队。
3）循环出队并计数已修课程，同时遍历其后继课程并降低入度。
4）某后继课程入度降到 0 时入队。
5）结束后若已修课程数等于 numCourses，返回 true，否则 false。
复杂度分析
时间复杂度：O(V + E)，其中 V = numCourses，E = prerequisites.length。
空间复杂度：O(V + E)，用于邻接表、入度数组和队列。
常见陷阱
- 把边方向写反，导致入度逻辑错误。
- 忘记初始化“无先修关系”的独立课程节点。
- 统计已处理课程数量时遗漏或重复计数。
- DFS 写法未正确标记访问状态（0/1/2），容易误判或栈溢出。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
int[] indegree = new int[numCourses];
for (int[] p : prerequisites) {
int a = p[0], b = p[1];
graph.get(b).add(a);
indegree[a]++;
}
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) q.offer(i);
}
int taken = 0;
while (!q.isEmpty()) {
int cur = q.poll();
taken++;
for (int nxt : graph.get(cur)) {
indegree[nxt]--;
if (indegree[nxt] == 0) q.offer(nxt);
}
}
return taken == numCourses;
}
}func canFinish(numCourses int, prerequisites [][]int) bool {
graph := make([][]int, numCourses)
indegree := make([]int, numCourses)
for _, p := range prerequisites {
a, b := p[0], p[1]
graph[b] = append(graph[b], a)
indegree[a]++
}
queue := make([]int, 0)
for i := 0; i < numCourses; i++ {
if indegree[i] == 0 {
queue = append(queue, i)
}
}
taken := 0
for head := 0; head < len(queue); head++ {
cur := queue[head]
taken++
for _, nxt := range graph[cur] {
indegree[nxt]--
if indegree[nxt] == 0 {
queue = append(queue, nxt)
}
}
}
return taken == numCourses
}class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
vector<int> indegree(numCourses, 0);
for (auto &p : prerequisites) {
int a = p[0], b = p[1];
graph[b].push_back(a);
indegree[a]++;
}
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) q.push(i);
}
int taken = 0;
while (!q.empty()) {
int cur = q.front();
q.pop();
taken++;
for (int nxt : graph[cur]) {
if (--indegree[nxt] == 0) q.push(nxt);
}
}
return taken == numCourses;
}
};from collections import deque
class Solution:
def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
graph = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
indegree[a] += 1
q = deque(i for i in range(numCourses) if indegree[i] == 0)
taken = 0
while q:
cur = q.popleft()
taken += 1
for nxt in graph[cur]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
q.append(nxt)
return taken == numCoursesvar canFinish = function(numCourses, prerequisites) {
const graph = Array.from({ length: numCourses }, () => []);
const indegree = new Array(numCourses).fill(0);
for (const [a, b] of prerequisites) {
graph[b].push(a);
indegree[a]++;
}
const queue = [];
for (let i = 0; i < numCourses; i++) {
if (indegree[i] === 0) queue.push(i);
}
let taken = 0;
for (let head = 0; head < queue.length; head++) {
const cur = queue[head];
taken++;
for (const nxt of graph[cur]) {
indegree[nxt]--;
if (indegree[nxt] === 0) queue.push(nxt);
}
}
return taken === numCourses;
};
Comments