algorithm - 为什么我的逻辑不能正确地用于 SPOJ TOPOSORT？

Question

给定的问题是http://www.spoj.com/problems/TOPOSORT/输出格式特别重要，因为:

Print "Sandro fails." if Sandro cannot complete all his duties on the list. 
If there is a solution print the correct ordering, 
the jobs to be done separated by a whitespace. 
If there are multiple solutions print the one, whose first number is smallest, 
if there are still multiple solutions, print the one whose second number is smallest, and so on. 

我所做的只是通过反转边来进行 dfs，即如果作业 A 在作业 B 之前完成，则存在从 B 到 A 的有向边。我通过对我创建的邻接列表进行排序并分别存储没有任何约束的节点来维护顺序，以便稍后以正确的顺序打印它们。使用了两个标志数组，一个用于标记已发现的节点，一个用于标记其所有邻居都已被探索的节点。

现在我的解决方案是http://www.ideone.com/QCUmKY (重要的功能是访问功能)并在正确运行 10 个案例后给出 WA，因此很难弄清楚我在哪里做错了，因为它运行了我手工完成的所有测试用例。

Answer 1

我认为这里的问题是 DFS 拓扑排序算法只能保证产生有效的拓扑排序，而不是字典顺序第一的拓扑排序(这是你需要的)。

可能解决此问题的一种方法是更改​​用于执行拓扑排序的算法。与其使用 DFS，不如考虑使用其他标准算法，该算法的工作原理是维护一组入度为 0 的所有节点，然后重复删除一个节点并更新入度为 0 的节点集。如果使用优先级队列来选择具有indegree 0 且每次迭代的数值最小，您将得到满足问题给定约束的拓扑排序。

希望这对您有所帮助!