写某个代码时使用的拓扑排序:
queue<int>q;
for(int i=1;i<=cnt;++i)
if(!in[i]) q.push(i);
while(!q.empty()){
int u=q.front();q.pop();
for(int v:gn[u]){
/*一些操作*/
if(--in[v]==0) q.push(v);
}
}
这个拓扑排序是在缩点后进行的,所以走的图一定是一个 DAG,然而跑完之后 in 数组不全为 0。
我以为可能是被减成负数了,但是我 assert 一遍之后发现是正数?
一个 DAG 拓扑排序完之后为啥入度数组里会有正数?
没想通,如果我是小丑请拷打我。