【HDU 1285】 确定比赛名次(拓扑排序+字典序)

26
Sep

【HDU 1285】 确定比赛名次(拓扑排序+字典序)

嘛,这题当时还是纠结了挺久的,后来发现其实很好做= =留作当字典序拓扑排的板子吧。。。

题面描述
给定一张图,要求输出字典序最小的拓扑排序结果
解题思路
基于拓扑排序的原理,即可以被选取的点的唯一原则就是其入度为0,那么改变以往每次处理所有所有点的过程,每次从前往后扫,将第一个入度为零的点选取并减去出边后,直接从头再次扫起就可以了。
代码编写
很简单,将拓扑排序模板中的循环改成选取一个点就跳出就好了。同时将函数的返回值改为一个vector数组,就做完了。

AC代码
https://paste.ubuntu.com/25616443/

由于个人水平有限,上述文字可能存在错误,如有问题,欢迎指正和讨论!

添加新评论