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

LCR 113. 课程表 II - 力扣LeetCde题目理解总共有numCourses门课编号0 ~ numCourses‑1。prerequisites[i] [a,b]学 a 课必须先学 b 课。要求返回任意一个合法上课顺序。存在拓扑序列无环返回上课顺序数组图有环循环依赖课学不完返回空数组和课程表 I 区别课程表 I 只需要判断 true/false本题需要把拓扑排序的序列输出出来。核心思路 BFS 拓扑排序建图邻接表b → ab 上完之后才可以上 a统计每门课的入度还有几门先修没上完入度为 0 全部入队列不需要先修、可以直接学的课程BFS 遍历取出队头课程加入结果集合代表这门课已经上完把它所有后继课程入度减一消除这门课带来的依赖如果后继课程入度变成 0说明它的全部先修课完成入队列最后判断如果结果数组长度等于总课程数全部课都上完直接返回结果长度不够说明有环返回空数组class Solution { public: vectorint findOrder(int numCourses, vectorvectorint prerequisites) { vectorvectorint edges(numCourses); // 临接表 vectorint in(numCourses,0); // 构建图 for (auto e : prerequisites) { int a e[0]; int b e[1]; edges[b].push_back(a); in[a]; } vectorint ret; queueint 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 {}; } };