【POJ 1094】 Sorting It All Out(拓扑排序)

26
Sep

【POJ 1094】 Sorting It All Out(拓扑排序)

个人感觉这是这几天做的拓扑排序题目里面最难的一题了,想了很久交了很多次,思路很有意思,记录一下。

题面描述
给定一组边,可能含重边。求问其是否能唯一拓扑排序,若可以,输出排序后的结果;若是有环,输出最少需要多少组关系就能确定环;如果不能唯一拓扑排序,输出不可排序,若同时也存在环,选择输出环的情况。
解题思路
这个题目的难点在于处理好环的情况,那么特别是题目要求输出判环所需关系的数量,那么我们不妨将所有输入的边都存起来,然后一个个加进图里,每次都跑一遍拓扑排序,如果出现了环那么这就是最少的关系数;如果一直把所有边都加完依然不能唯一排序也不能找到环,那么便是最后一种情况了
代码编写
首先读入的时候要将所有的边通过一个数组存起来,然后依次添加进图。再topo()函数中维护一个ma值,代表队列的长度最大值,如果在最后其的值大于1,那么就是存在不唯一图。返回值部分,返回三种值,对于环或成立的返回值,在主函数中立即作为答案输出;若是不唯一,则一直继续加边,到最后输出不能确定唯一图即可。

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

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

添加新评论