[拓扑排序]leetcode210：课程表 Ⅱ (medium)

课程表 Ⅱ (medium)"/>

[拓扑排序]leetcode210：课程表 Ⅱ (medium)

题目：

题解：

• 拓扑排序，与207. 课程表代码一样的，只是将拓扑排序的顶点保留而已，注意边的数组给的是反向，这样的话，我们要将res反转就行了。
• 算法步骤：
• 1）遍历边的数组prerequisites建立图的邻接表
• 2）使用队列来存放入度为0的顶点，从而避免重复检测入度为0的顶点
• 3）删除入度为0的点，以及删除该点为起点的边，并统计删除入度为0的顶点个数
• 4）若有向图无环，则res.size()等于顶点数numCounses；否则有向图有环，则res.size()会小于顶点数numCounses

---

拓扑排序算法思路：

• 1）在有向图中选一个入度为0的顶点且输出之
• 2）从图中删除该顶点和所有以它为弧尾的弧
• 3）重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。=后者表示的是该有向图存在环。

代码如下：

// 2022/4/8 代码
vector<int> graph[2010];
class Solution {
public:// 对有向无环图进行拓扑排序vector<int> findOrder(int n, vector<vector<int>>& g) {//for(int i=0;i<n;++i)graph[i].resize(0);fill(graph, graph+2010, vector<int>());vector<int> res,indegrees(n);for(auto& edge:g){graph[edge[1]].push_back(edge[0]);indegrees[edge[0]]++;}queue<int> q;// 入度为0的顶点入队列for(int i=0;i<n;++i){if(!indegrees[i])q.push(i);}// 开始进行bfswhile(q.size()){auto i=q.front();q.pop();// 在res中添加拓扑序列的顶点res.push_back(i);// 删除 i->j 的所有邻接边for(int j:graph[i]){if(--indegrees[j]==0)q.push(j);}}return res.size()==n?res:vector<int> ();}
};