Today is a Saturday Deep Dive day. The scheduled review is superseded by the deep dive:
📄 See: 2026-08-08-deepdive.md — 拓扑排序 / Topological Sort (Course Schedule I & II)
The deep dive covers LeetCode 207 & 210 in full depth with Kahn's BFS, DFS 3-color marking, edge cases, real-world applications (npm, Airflow, Kubernetes), and interview simulation.
🔬 Saturday Deep Dive: 拓扑排序 — Course Schedule I & II (17 min read)
📊 NeetCode: 86/150 · SysDesign: 60/40 · Behavioral: 60/40 · Frontend: 37/50 · AI: 30/30
🔥 109-day streak!
中文：
拓扑排序是处理有向无环图（DAG）中依赖关系的核心算法。你学课程 A 之前必须先学课程 B——这类问题天生就是拓扑排序。它在 npm、pip、Maven 等包管理器，CI/CD 流水线，以及数据库迁移顺序中无处不在。
关键洞察：如果图中存在环（A 依赖 B，B 又依赖 A），则不可能完成所有任务——检测环就是这道题的另一半。
🔗 LeetCode 207 — Course Schedule: https://leetcode.com/problems/course-schedule/
🔗 LeetCode 210 — Course Schedule II: https://leetcode.com/problems/course-schedule-ii/
📹 NeetCode 207: https://www.youtube.com/watch?v=EgI5nU9etnU
📹 NeetCode 210: https://www.youtube.com/watch?v=Akt3glAwyfY
English:
Topological sort produces a linear ordering of a DAG's nodes such that every dependency appears before the node depending on it. It is the backbone of package managers, build systems, task schedulers, and database migration tools.
If a cycle exists — A depends on B depends on A — no valid ordering exists. Detecting that is half the problem and where most interview candidates trip.
有向无环图（DAG）
图中的边有方向性，且不存在环。
prerequisites = [[1,0]] 表示"要学课程 1，必须先学课程 0"，边是 0 → 1（0 是前置）。
入度（In-degree）
一个节点的入度 = 有多少个节点指向它。
入度为 0 的节点 = 没有前置依赖，可以立即处理。
两种经典方法
- 找到所有入度为 0 的节点，加入队列
- 每次取出一个节点，将其邻居的入度减 1
- 邻居入度变为 0 → 加入队列
- 白色 = 未访问；灰色 = 正在访问（在当前 DFS 路径上）；黑色 = 完成
- 遇到灰色节点 → 检测到环
- 后序（post-order）收集节点，结果即拓扑序
心智模型：
Kahn's = 反复"剥离"没有依赖的节点（像剥洋葱）
DFS = 深入到叶子节点，最先完成的最靠后，反转即是正确顺序A DAG (Directed Acyclic Graph) has directed edges and no cycles.
Topological sort gives a linear ordering where for every directed edge u → v, u appears before v.
In-degree = number of incoming edges to a node. Zero in-degree means "no prerequisites."
Two canonical approaches:
| Kahn's (BFS) | DFS (3-color) | |
|---|---|---|
| Intuition | Peel off dependency-free nodes | Go deep; finish-order reversed = topo-order |
| Cycle detection | processed < n at the end | Back edge to VISITING node |
| Returns order? | Yes, directly | Yes, via post-order collection |
| Preferred for? | Interviews (transparent) | When DFS is already required |
Time & Space: O(V + E) for both.
中文： Kahn's 算法直观、易调试，还能直接检测环路。面试时优先使用。
from collections import deque
from typing import List
def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
"""
LeetCode 207: Can you finish all courses?
Return True if the prerequisite graph has no cycle.
Example:
numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]]
Edges: 0->1, 0->2, 1->3, 2->3 (valid DAG)
"""
# Build adjacency list: adj[prereq] = [courses that need this prereq]
adj = [[] for _ in range(numCourses)]
in_degree = [0] * numCourses
for course, prereq in prerequisites:
adj[prereq].append(course) # prereq must come BEFORE course
in_degree[course] += 1 # course has one more prerequisite
# Start with all courses that have zero prerequisites
queue = deque(c for c in range(numCourses) if in_degree[c] == 0)
processed = 0
while queue:
course = queue.popleft()
processed += 1
for next_course in adj[course]:
in_degree[next_course] -= 1 # one fewer prereq needed
if in_degree[next_course] == 0:
queue.append(next_course) # now ready to take
# If all courses processed → no cycle → can finish
return processed == numCourses
def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
"""
LeetCode 210: Return the actual valid course order, or [] if impossible.
Identical to canFinish — just collect the processing order.
"""
adj = [[] for _ in range(numCourses)]
in_degree = [0] * numCourses
for course, prereq in prerequisites:
adj[prereq].append(course)
in_degree[course] += 1
queue = deque(c for c in range(numCourses) if in_degree[c] == 0)
order = []
while queue:
course = queue.popleft()
order.append(course) # record the order — only new line vs canFinish
for next_course in adj[course]:
in_degree[next_course] -= 1
if in_degree[next_course] == 0:
queue.append(next_course)
# If we couldn't process all courses, a cycle exists
return order if len(order) == numCourses else []中文： DFS 方法用三种状态标记每个节点。面试官要求 DFS 时用这套写法。
def findOrder_dfs(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
"""
DFS-based topological sort with 3-color marking.
State encoding:
0 = UNVISITED (white) — not yet explored
1 = VISITING (gray) — on the current DFS stack; back edge here = CYCLE
2 = VISITED (black) — fully processed, safe
"""
# Build: adj[course] = [prerequisites of this course]
# (Direction: course → what it needs)
adj = [[] for _ in range(numCourses)]
for course, prereq in prerequisites:
adj[course].append(prereq)
state = [0] * numCourses # all start UNVISITED
result = []
def dfs(node: int) -> bool:
"""Returns False if a cycle is detected."""
if state[node] == 1:
return False # Back edge to current stack → CYCLE
if state[node] == 2:
return True # Already processed → skip safely
state[node] = 1 # Mark VISITING (on current stack)
for prereq in adj[node]:
if not dfs(prereq):
return False # Propagate cycle detection up
state[node] = 2 # Mark VISITED (done)
result.append(node) # Post-order: node added AFTER all its prerequisites
return True
# Handle disconnected components — try every node
for course in range(numCourses):
if state[course] == 0:
if not dfs(course):
return [] # Cycle found
# result is already in valid topological order
# (prereqs get added first because we go deep before adding current node)
return resultInput: numCourses=3, prerequisites=[[1,0],[2,1]]
Meaning: to take 1, first take 0; to take 2, first take 1.
Diagram and code produce identical results. ✅
中文：常见陷阱
1. 边方向搞反了（最高频错误！）
prerequisites = [[1, 0]] 表示"学课程 1 之前先学课程 0"。
正确写法：adj[prereq].append(course)，而非 adj[course].append(prereq)。
错误方向会导致所有依赖颠倒，环检测也会失效。
2. 孤立节点
某些课程可能不出现在 prerequisites 里。
必须遍历 range(numCourses) 而不是只遍历 prerequisites 中的节点。
否则孤立课程的入度永远不被初始化，或在 DFS 中永远不被访问。
3. 自环
[[0, 0]] — 课程 0 以自己为前置条件。
Kahn's：in_degree[0] 初始为 1 且永远不会到 0，自然无法处理。
DFS：第一次 dfs(0) 就将 state[0] 设为 1，再次访问 0 时检测到环。
4. 多个合法顺序
当多个节点同时入度为 0 时，顺序不唯一。
LeetCode 207/210 接受任意合法答案。
如果题目要求字典序最小，改用 heapq 代替 deque（复杂度变 O((V+E)logV)）。
5. prerequisites 为空
完全合法——所有课程都可以任意顺序学习。
不要漏掉这个基础情况：返回 True（207）或 list(range(numCourses))（210）。
English: Key Gotchas
[course, prereq] pair means prereq → course. Reversing this is the #1 interview bug.n courses, not just those in prerequisites.[[0,0]]. Both algorithms handle naturally but it's worth calling out.中文：生产环境中的拓扑排序
拓扑排序无处不在，只是不一定叫这个名字：
包管理器（npm / pip / Maven）
安装包 A 之前先安装 A 的所有依赖。npm 用拓扑排序决定安装顺序，循环依赖时报错 "circular dependency detected"。
构建系统（Makefile / Bazel / Gradle）
make 分析构建目标之间的依赖关系，只编译需要的文件，且按正确顺序编译。Bazel 的整个构建图就是一个被持续维护的 DAG。
数据库迁移
先创建被引用的表（父表），再创建带外键的表（子表）。Alembic / Flyway 在内部对迁移文件做拓扑排序，同时检测迁移图中的循环。
Kubernetes 资源部署
先部署 ConfigMap 和 Secret，再部署依赖它们的 Deployment。ArgoCD 的 sync-wave 正是拓扑排序在 K8s 中的应用。
Apache Airflow / Temporal / Prefect
工作流调度的核心——只有当所有上游任务完成，下游任务才能启动。Airflow DAG 的命名就来自拓扑排序的基础数据结构。
English:
The universal pattern: Any "X must happen before Y" constraint set across tasks → build a graph, topologically sort it.
Scenario: "You have n tasks and a list of [task, dependency] pairs. Return a valid execution order, or an empty list if impossible."
Q1: Walk me through your approach before writing any code.
Q2: What if there's a cycle?
→ "Kahn's handles it naturally. Nodes in a cycle always have at least one incoming edge from within the cycle, so their in-degree never reaches zero. They never get enqueued. After the BFS, len(order) < n tells me a cycle exists. No extra cycle-detection code needed — it falls out of the algorithm for free."
Q3: Which tasks can run in parallel?
→ "All tasks enqueued in the same BFS 'round' have no dependencies on each other — they can run concurrently. Process the queue level by level instead of node by node:"
def parallel_order(n: int, deps: List[List[int]]) -> List[List[int]]:
"""Returns execution waves; tasks in same wave run in parallel."""
adj = [[] for _ in range(n)]
in_degree = [0] * n
for task, prereq in deps:
adj[prereq].append(task)
in_degree[task] += 1
queue = deque(t for t in range(n) if in_degree[t] == 0)
waves = []
while queue:
wave_size = len(queue) # snapshot current level
wave = []
for _ in range(wave_size):
task = queue.popleft()
wave.append(task)
for nxt in adj[task]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
waves.append(wave)
return waves if sum(len(w) for w in waves) == n else []
# e.g. [[0,1], [2,3], [4]] — first two tasks run in parallel, etc.Q4: How is this different from regular BFS/DFS on an undirected graph?
→ "Direction is fundamental. Regular BFS on an undirected graph finds shortest paths — edges have no inherent ordering. Topological sort only applies to directed graphs with no cycles. The BFS here isn't finding shortest paths; it's finding a processing order that respects dependency direction. You can't topologically sort a tree or undirected graph meaningfully."
Q5: What's the time/space complexity? Where does it break down in practice?
→ "O(V+E) time — each node and edge visited exactly once. O(V+E) space for adjacency list + O(V) for in-degree and queue. The algorithm itself is never the bottleneck. In practice: (1) building the dependency graph from a database or config system can be slow — that's the I/O bottleneck; (2) if the graph has millions of nodes, the adjacency list memory dominates; (3) for very wide DAGs (many parallel tasks), queue overhead matters. The algorithm is essentially optimal — you can't do better than O(V+E) since you must read every edge at least once."
ASCII Diagram shows:
Code trace (findOrder Kahn's):
adj={0:[1],1:[2],2:[]}, in_degree=[0,1,1]queue=deque([0])len([0,1,2])==3==numCourses → return [0,1,2] ✓Diagram flow and code execution are identical. ✅