拓扑排序后的入度数组
  • 板块学术版
  • 楼主Yusani_huh
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/8/10 16:57
  • 上次更新2023/11/3 04:40:52
查看原帖
拓扑排序后的入度数组
239895
Yusani_huh楼主2023/8/10 16:57

写某个代码时使用的拓扑排序:

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 拓扑排序完之后为啥入度数组里会有正数?

没想通,如果我是小丑请拷打我。

2023/8/10 16:57
加载中...