LeetCode 210: Course Schedule II (Topological Sort with Kahn BFS)
LeetCode 210GraphTopological SortToday we solve LeetCode 210 - Course Schedule II.
Source: https://leetcode.com/problems/course-schedule-ii/
English
Problem Summary
Given numCourses and prerequisite pairs [a, b] (must take b before a), return one valid order to finish all courses. If impossible, return an empty array.
Key Insight
This is a directed graph ordering problem. Build edges b -> a. Any course with indegree 0 has all prerequisites satisfied and can be taken now. Repeatedly removing indegree-0 nodes gives a topological order.
Brute Force and Limitations
Trying all permutations is factorial and infeasible. DFS with backtracking can work but is verbose for order output and cycle handling. Kahn's BFS-style topological sort is direct and linear.
Optimal Algorithm Steps
1) Create adjacency list and indegree array.
2) Push all nodes with indegree 0 into a queue.
3) Pop queue front, append to answer, relax outgoing edges.
4) When neighbor indegree becomes 0, enqueue it.
5) If answer size is numCourses, return it; otherwise a cycle exists, return empty array.
Complexity Analysis
Time: O(V + E).
Space: O(V + E).
Common Pitfalls
- Reversing edge direction (should be prerequisite to dependent).
- Forgetting isolated courses (no incoming/outgoing edges).
- Returning partial order when cycle exists.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public int[] findOrder(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]++;
}
ArrayDeque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) q.offer(i);
}
int[] order = new int[numCourses];
int idx = 0;
while (!q.isEmpty()) {
int cur = q.poll();
order[idx++] = cur;
for (int nxt : graph.get(cur)) {
if (--indegree[nxt] == 0) q.offer(nxt);
}
}
return idx == numCourses ? order : new int[0];
}
}func findOrder(numCourses int, prerequisites [][]int) []int {
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]++
}
q := make([]int, 0)
for i := 0; i < numCourses; i++ {
if indegree[i] == 0 {
q = append(q, i)
}
}
order := make([]int, 0, numCourses)
for head := 0; head < len(q); head++ {
cur := q[head]
order = append(order, cur)
for _, nxt := range graph[cur] {
indegree[nxt]--
if indegree[nxt] == 0 {
q = append(q, nxt)
}
}
}
if len(order) != numCourses {
return []int{}
}
return order
}class Solution {
public:
vector<int> findOrder(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);
}
vector<int> order;
order.reserve(numCourses);
while (!q.empty()) {
int cur = q.front();
q.pop();
order.push_back(cur);
for (int nxt : graph[cur]) {
if (--indegree[nxt] == 0) q.push(nxt);
}
}
if ((int)order.size() != numCourses) return {};
return order;
}
};from collections import deque
class Solution:
def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
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)
order = []
while q:
cur = q.popleft()
order.append(cur)
for nxt in graph[cur]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
q.append(nxt)
return order if len(order) == numCourses else []var findOrder = 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);
}
const order = [];
for (let head = 0; head < queue.length; head++) {
const cur = queue[head];
order.push(cur);
for (const nxt of graph[cur]) {
indegree[nxt]--;
if (indegree[nxt] === 0) queue.push(nxt);
}
}
return order.length === numCourses ? order : [];
};中文
题目概述
给定课程总数 numCourses 与先修关系 [a, b]（学 a 前要先学 b），请返回一个可行的修课顺序；若无法完成全部课程，返回空数组。
核心思路
把课程关系建成有向图，边方向是 b -> a。入度为 0 的课程代表当前没有未满足的前置条件，可以立即学习。不断移除入度为 0 的点即可得到拓扑序。
暴力解法与不足
暴力枚举所有课程排列是阶乘复杂度，完全不可行。DFS 回溯虽然能做，但输出顺序与判环处理更繁琐。Kahn 拓扑排序（BFS 版）更直观且线性复杂度。
最优算法步骤
1）建立邻接表和入度数组。
2）把所有入度为 0 的课程入队。
3）循环出队：加入答案，并遍历其出边。
4）相邻课程入度减 1，若变为 0 则入队。
5）若最终答案长度等于 numCourses，返回答案；否则存在环，返回空数组。
复杂度分析
时间复杂度：O(V + E)。
空间复杂度：O(V + E)。
常见陷阱
- 边方向写反（应从先修课指向后续课）。
- 忽略孤立课程，导致结果长度不足。
- 图中有环时误返回部分顺序。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public int[] findOrder(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]++;
}
ArrayDeque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) q.offer(i);
}
int[] order = new int[numCourses];
int idx = 0;
while (!q.isEmpty()) {
int cur = q.poll();
order[idx++] = cur;
for (int nxt : graph.get(cur)) {
if (--indegree[nxt] == 0) q.offer(nxt);
}
}
return idx == numCourses ? order : new int[0];
}
}func findOrder(numCourses int, prerequisites [][]int) []int {
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]++
}
q := make([]int, 0)
for i := 0; i < numCourses; i++ {
if indegree[i] == 0 {
q = append(q, i)
}
}
order := make([]int, 0, numCourses)
for head := 0; head < len(q); head++ {
cur := q[head]
order = append(order, cur)
for _, nxt := range graph[cur] {
indegree[nxt]--
if indegree[nxt] == 0 {
q = append(q, nxt)
}
}
}
if len(order) != numCourses {
return []int{}
}
return order
}class Solution {
public:
vector<int> findOrder(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);
}
vector<int> order;
order.reserve(numCourses);
while (!q.empty()) {
int cur = q.front();
q.pop();
order.push_back(cur);
for (int nxt : graph[cur]) {
if (--indegree[nxt] == 0) q.push(nxt);
}
}
if ((int)order.size() != numCourses) return {};
return order;
}
};from collections import deque
class Solution:
def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
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)
order = []
while q:
cur = q.popleft()
order.append(cur)
for nxt in graph[cur]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
q.append(nxt)
return order if len(order) == numCourses else []var findOrder = 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);
}
const order = [];
for (let head = 0; head < queue.length; head++) {
const cur = queue[head];
order.push(cur);
for (const nxt of graph[cur]) {
indegree[nxt]--;
if (indegree[nxt] === 0) queue.push(nxt);
}
}
return order.length === numCourses ? order : [];
};
Comments