博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
拓扑排序
阅读量:4330 次
发布时间:2019-06-06

本文共 1194 字,大约阅读时间需要 3 分钟。

#include 
using namespace std;const int maxn = 5e5 + 10;int N, M;int h[maxn], v[maxn], in[maxn], nx[maxn];int sz = 0;void init() { for(int i = 1; i <= N; i ++) { h[i] = -1; in[i] = 0; } sz = 0;}void add(int a, int b) { v[sz] = b; nx[sz] = h[a]; h[a] = sz; in[b] ++; sz ++;}void TopSort() { queue
q; vector
ans; for(int i = 1; i <= N; i ++) { if(in[i] == 0) q.push(i); } while(!q.empty()) { int tp = q.front(); q.pop(); ans.push_back(tp); for(int i = h[tp]; i != -1; i = nx[i]) { in[v[i]] --; if(in[v[i]] == 0) q.push(v[i]); } } if(ans.size() != N) printf("NO\n"); else { for(int i = 0; i < ans.size(); i ++) printf("%d%s", ans[i], i != ans.size() - 1 ? " " : "\n"); }}int main() { while(~scanf("%d%d", &N, &M)) { init(); for(int i = 0; i < M; i ++) { int a, b; scanf("%d%d", &a, &b); add(a, b); } TopSort(); } return 0;}

  see u again

转载于:https://www.cnblogs.com/zlrrrr/p/10743897.html

你可能感兴趣的文章
【转】轻松记住大端小端的含义(附对大端和小端的解释)
查看>>
设计模式那点事读书笔记(3)----建造者模式
查看>>
ActiveMQ学习笔记(1)----初识ActiveMQ
查看>>
Java与算法之(2) - 快速排序
查看>>
Windows之IOCP
查看>>
机器学习降维之主成分分析
查看>>
CTP2交易所成交回报
查看>>
WebSocket & websockets
查看>>
openssl 升级
查看>>
ASP.NET MVC:通过 FileResult 向 浏览器 发送文件
查看>>
CVE-2010-2883Adobe Reader和Acrobat CoolType.dll栈缓冲区溢出漏洞分析
查看>>
使用正确的姿势跨域
查看>>
AccountManager教程
查看>>
Android学习笔记(十一)——从意图返回结果
查看>>
算法导论笔记(四)算法分析常用符号
查看>>
ultraedit激活
查看>>
总结(6)--- python基础知识点小结(细全)
查看>>
亿级曝光品牌视频的幕后设定
查看>>
ARPA
查看>>
JSP开发模式
查看>>