【剑斩OFFER】算法的暴力美学——力扣 210 题：课程表 Ⅱ
一、题目描述
二、算法原理
思路：使用拓扑排序
入度：指向该数字的个数
出度：箭尾的个数
拓扑排序：步步的把入度为 0 的值移除或记录下来：
最移除或记录完所有的节点，如果：
像这种没有节点的入度为 0 的，就跟题目说的：永远都是学不完，进入了一个死循环；
三、代码实现
class Solution {
public:
vector findOrder(int n, vector>& prerequisites) {
vector> edge(n);//邻接表
vector in(n);//每个节点的入度值
//使用拓扑排序
for(auto& e : prerequisites)
{
int a = e[0],b = e[1];// b->a 2->1
edge[b].push_back(a);
in[a]++;
}
queue que;
vector ret;//最终答案
for(int i = 0; i < n; i++)
{
if(in[i] == 0)
{
ret.push_back(i);
que.push(i);//入 a
}
}
//使用 BFS 算法
while(que.size())
{
int target = que.front();
que.pop();
for(auto& e : edge[target])
{
in[e]--;//断开链接节点
if(in[e] == 0)
{
que.push(e);
ret.push_back(e);
}
}
}
for(auto& e : in)//有环
{
if(e) return {};
}
return ret;
}
};
