是什么
有向图中,对所有的节点进行排序,要求没有一个节点指向它前面的节点。
怎么做
步骤
- 遍历到所有入度为0的节点,加入队列;如果没有这样的点,说明有向图构成环,则该图无解,结束算法
- 找到与第1步找到的相邻节点,相邻节点入度-1
- 元素出队,执行第1步
- 所有节点入度都为0后,结束算法
模板
queue<int>q;
for(int i=0;i<n;i++){//n:节点的总数
if(in[i]==0){
q.push(i);
}
} //将入度为0的节入队
vector<int>ans;//ans:为拓扑序列
while(!q.empty()){
int p=q.top();
q.pop();//选一个入度为0的节点出队
ans.push_back(p);
for(int i=0;i<edge[p].size();i++){
int y=edge[p][i];
in[y]--;
if(in[y]==0){
q.push(y);
}
}
}
if(ans.size()==n){
for(int i=0;i<ans.size();i++){
cout<<ans[i];
}
cout<<endl;
}else{
cout<<"No Answer!"<<endl;//ans中的长度与n不相等,就说明无解
}
例题
洛谷P1038 神经网络
洛谷P1113 杂务
洛谷P1137 旅行计划
洛谷P1983 车站分级
洛谷P3243 [HNOI2015]菜肴制作
洛谷P4017 最大食物链计数