算法日常・每日刷题--＜BFS拓扑排序＞4

LCR 113. 课程表 II - 力扣（LeetCde）

题目理解

总共有numCourses门课，编号0 ~ numCourses‑1。prerequisites[i] = [a,b]：学 a 课，必须先学 b 课。

要求返回任意一个合法上课顺序。

• 存在拓扑序列（无环）：返回上课顺序数组
• 图有环（循环依赖，课学不完）：返回空数组

和课程表 I 区别：课程表 I 只需要判断 true/false；本题需要把拓扑排序的序列输出出来。

核心思路 BFS 拓扑排序

1. 建图（邻接表）：b → a，b 上完之后才可以上 a；统计每门课的入度（还有几门先修没上完）
2. 入度为 0 全部入队列：不需要先修、可以直接学的课程
3. BFS 遍历
   • 取出队头课程，加入结果集合（代表这门课已经上完）
   • 把它所有后继课程入度减一（消除这门课带来的依赖）
   • 如果后继课程入度变成 0，说明它的全部先修课完成，入队列
4. 最后判断
   • 如果结果数组长度等于总课程数：全部课都上完，直接返回结果
   • 长度不够：说明有环，返回空数组

class Solution { public: vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { vector<vector<int>> edges(numCourses); // 临接表 vector<int> in(numCourses,0); // 构建图 for (auto e : prerequisites) { int a = e[0]; int b = e[1]; edges[b].push_back(a); in[a]++; } vector<int> ret; queue<int> q; for (int i = 0; i < numCourses; i++) { if (in[i] == 0) { q.push(i); } } while (q.size()) { int a = q.front(); q.pop(); ret.push_back(a); for (auto next : edges[a]) { // 将有关边的入度-- in[next]--; if (in[next] == 0) { q.push(next); } } } if (ret.size() == numCourses) return ret; else return {}; } };