震惊,全世界都会拓扑排序了,就我不会

当我在改这道题的时候。

我写了一个(我自己)看起来很对的拓扑排序。

然后就拿到了20分的好成绩。

于是我向神犇Liu_yi_tong求助。

神犇把那个“拓 扑 排 序”改成了这样。

我:???

神犇:你写的不是拓扑排序啊

我:???

神犇:你写的是SPFA啊

我:???

然后我就想起来了拓扑排序怎么写。

然后就A了。

SPFA是要让每个元素在每次被更新之后就入队更新其他元素,因此要入队多次。

而拓扑排序一定是要让当前元素被更新到不能被更新了之后再入队更新其他元素,因此每个元素只会入队一次。

至于我第一次写的缝合怪代码,是因为只记住了拓扑排序每个元素只入队一次的性质,却忘了这个性质成立的前提。

比如我们考虑这个图:

如果按照我的错误写法,比如先用5更新3,3入队。那么以后如果2再更新3的话,因为3已经入队了,这样就会造成3以后的答案错误。

原文地址:https://www.cnblogs.com/wwcdcpyscc/p/13773674.html