AcWing 848. 有向图的拓扑序列
2021-03-01 06:27
阅读:628
标签:操作 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
文章来自:搜素材网的编程语言模块,转载请注明文章出处。
文章标题:AcWing 848. 有向图的拓扑序列
文章链接:http://soscw.com/index.php/essay/58438.html
文章标题:AcWing 848. 有向图的拓扑序列
文章链接:http://soscw.com/index.php/essay/58438.html
评论
亲,登录后才可以留言!