6

给定的问题是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，所以很难弄清楚我在哪里做错了，因为它运行对于我手工完成的所有测试用例。

4

3 回答 3

5

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

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

希望这可以帮助！

于 2013-07-01T18:14:30.430 回答
4

这是破坏您的程序的一个输入：

4 4
2 4
4 1
3 1

答案应该是 2 3 4 1，但您的代码会打印 3 2 4 1。

原因是你按索引顺序访问顶点；但是，更高阶的索引可能会导致低索引节点。

这个问题应该有一个简单的 O(m + nlogn) 解决方案，但我看不出如何轻松修复您的代码。自编写以来，您对这段代码最了解，所以祝您修复它好运。

于 2013-07-01T17:03:45.057 回答
2

The dfs algorithm times out in this particular question. With some clever tricks you can get the complexity of the solution to O(m). You need to eliminate the sort that you are using to sort all the edges in order. I maintained a list of reverse edges, i.e for two edges u->v and w->v, I initially added them in the list li[v]->u->w. and then traversing from 1 to n, I created the corrected directed edges, but this time they come out to be automatically in order.

Anyway this times out(on test case12 for me). You need a very optimized algorithm for this. The algorithm templatetypedef mentions works fine, probably the recursion overhead in dfs is a bit too much in the dfs algorithm.

The idea is really simple, you can read about this here http://en.wikipedia.org/wiki/Topological_sorting

Basically, you can complete the tasks with zero indegree and once the task is completed, you remove all the outgoing edges and update all the indegrees and find another task with zero indegree. To get things in order, you can use a priority queue.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int indeg[10005];
int topo[10005];
vector <int> g[10005];
int main(){
        int n,m;
        int cur= 0;
        cin >> n >> m;
        for (int i = 0; i < m; i++){
                int x,y;
                scanf("%d %d" ,&x, &y);
                indeg[y]++;
                g[x].push_back(y);
        }
        priority_queue <int> q;
        for(int i = 1; i <= n; i++)
                if (!indeg[i]) q.push(-1*i);
        while(!q.empty()){
                int nd = -1 * q.top();
                q.pop();
                for(int i = 0; i < g[nd].size(); i++){
                        indeg[g[nd][i]]--;
                        if (!indeg[g[nd][i]])
                                q.push(-1*g[nd][i]);
                }
                topo[cur++] = nd;
        }
        if (cur!= n){
                cout << "Sandro fails." << endl;
                return 0;
        }

        for(int i = 0; i < n-1; i++)
                printf("%d ", topo[i]);
        printf("%d\n", topo[n-1]);


        return 0;
}
于 2013-07-02T19:25:56.323 回答