【LeetCode 第207题】

LeetCode 207 课程表（拓扑排序 + 邻接表实现）题解

题目描述

题目理解
这道题本质是在问：

给你一堆课程依赖关系，能不能把所有课程都学完？

比如：

• [1, 0]表示：学 1 之前必须先学 0
• 也就是：0 → 1

问题就变成：

👉这个有向图中是否存在环？

• 有环 ❌ → 一定学不完（死循环）
• 无环 ✅ → 可以学完（存在拓扑序）

二、核心思路：拓扑排序（Kahn算法）

我们用入度 + BFS（或栈模拟）来做：

步骤：

1. 建图（邻接表）

2. 统计每个点的入度

3. 把所有入度为 0 的点加入队列

4. 每次取一个点：

   • 删除它（模拟学完）
   • 它指向的点入度减 1
   • 如果某个点入度变成 0 → 入队

5. 最后看：

   • 能不能把所有点都删掉

三、代码实现解析（重点）

手写邻接表 + 拓扑排序，ACM 风格 👍

1. 邻接表结构

inth[N],e[N],ne[N],idx;

含义：

加边函数

voidadd(inta,intb){e[idx]=b;ne[idx]=h[a];h[a]=idx++;}

表示：
👉 从a → b

2. 建图 + 入度统计

for(auto&edge:prerequisites){intai=edge[0];intbi=edge[1];add(bi,ai);// bi → aiin[ai]++;}

解释：

• [ai, bi]表示：bi → ai

• 所以：

  • 加边bi → ai
  • ai入度 +1

3. 初始化队列（入度为 0）

for(inti=0;i<numCourses;i++){if(in[i]==0){q.push_back(i);s.insert(i);st[i]=true;}}

这里做了三件事：

• q：模拟队列（你用 vector 当栈用）
• s：记录访问过的节点
• st：防止重复入队

4. 拓扑排序过程

while(!q.empty()){intu=q.back();q.pop_back();for(inti=h[u];i!=-1;i=ne[i]){intv=e[i];in[v]--;if(in[v]==0&&!st[v]){st[v]=true;s.insert(v);q.push_back(v);}}}

流程：

1. 取一个入度为 0 的点u
2. 遍历它的所有邻居v
3. 入度--
4. 如果变成 0 → 加入队列

5. 判断是否有环

returns.size()==numCourses;

解释：

• 如果所有点都被“删除”（拓扑排序成功）
  →s.size() == n
• 否则说明：
  → 有环 ❌

四、复杂度分析

• 时间复杂度：
  👉O(n + m)
• 空间复杂度：
  👉O(n + m)

其中：

• n：课程数
• m：依赖关系数

五、一些关键理解点

1️⃣ 为什么入度为 0 可以学？

因为：

👉 没有任何课程依赖它

2️⃣ 为什么能检测环？

如果有环：

0 → 1 → 2 → 0

那每个点入度都 ≥ 1
👉永远没有入度为 0 的点

➡️ 拓扑排序无法开始 / 中途卡住

六、总结

一句话总结这题：

判断有向图是否有环 → 用拓扑排序

七、推荐优化（可写进进阶部分）

其实可以把这部分简化：

unordered_set<int>s;boolst[N];

👉 完全可以换成：

intcnt=0;

每处理一个点：

cnt++;

最后：

returncnt==numCourses;

更轻量、更高效 👍