Kav*_*edi 6 algorithm graph depth-first-search topological-sort
给出的问题是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,所以很难弄清楚我在哪里做错了因为它运行对于我手工完成的所有测试用例.
我认为这里的问题是DFS拓扑排序算法只能保证产生有效的拓扑排序,而不是按字典顺序排列的第一拓扑排序(这就是你需要的).
您可以解决此问题的一种方法是更改您用于执行拓扑排序的算法.而不是使用DFS,请考虑使用其他标准算法,该算法通过维护一组具有indegree 0的所有节点,然后重复删除一个并更新具有indegree 0的节点集来工作.如果使用优先级队列来选择具有indecree 0并且在每次迭代时具有最低数值,您将返回满足问题给出的约束的拓扑排序.
希望这可以帮助!