AcWing 848. 有向图的拓扑序列

2021-03-01 06:27

阅读：499

标签：操作 cpp oid 导致 while pre space 配套有向图

AcWing 848. 有向图的拓扑序列

用BFS来写拓扑，以前还真没想过这个思路
之前用的都是深搜找拓扑序

依然是正常用数组实现一个邻接表，然后用数组模拟队列，从入度为0，即d[i] == 0的点开始搜索
用数组模拟队列的原因是为了最后方便直接输出拓扑序，就不用另开一个数组专门存储了

代码中的几个小细节：

把邻接表的头指针初始化为-1, memset(h, -1, sizeof h);,来表示邻接表为空，不然会死循环导致TLE
往队列中添加元素的操作是q[++tt] = i;，弹出元素则是hh++;或者t = q[hh++];,和这几个操作配套的一个细节是要把队尾初始为-1,int hh = 0, tt = -1;

示例代码里有很多short cut, 感觉不熟练容易写歪来= =, 比如我老是忘记初始化h[]数组，然后写完要补上一行 QwQ

代码实现

#include 
#include 
#include 
#include 

using namespace std;

const int N = 100010;

int h[N], e[N], ne[N], idx;
int q[N], d[N];
int n, m;

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool toposort(){
    int hh = 0, tt = -1;

    for(int i = 1; i

AcWing 848. 有向图的拓扑序列

标签：操作 cpp oid 导致 while pre space 配套有向图

原文地址：https://www.cnblogs.com/love-lucy/p/14401883.html

上一篇：自己动手写窗体设计器之Vb.net篇

下一篇：windows如何查看端口占用情况？

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 848. 有向图的拓扑序列
文章链接：http://soscw.com/index.php/essay/58438.html

亲，登录后才可以留言！

AcWing 848. 有向图的拓扑序列

AcWing 848. 有向图的拓扑序列

代码实现

评论

热门文章

推荐文章

最新文章

置顶文章