爲什麼我的邏輯無法正確運行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. 

我在做什麼通過逆轉的邊緣即，如果作業的作業B之前完成是簡單地做DFS，有一個從有向邊B到A。我通過對我創建的鄰接表進行排序並存儲沒有任何約束的節點來維護順序，以便以後按照正確的順序打印它們。有兩個標誌陣列使用，一個用於標記發現節點，另一個用於標記已探索所有鄰居的節點。

現在我的解決方案是http://www.ideone.com/QCUmKY（其中重要的功能是訪問函數），並且在運行正確的10個案例之後給出WA，所以它真的很難弄清楚我在哪裏做錯了，因爲它運行所有測試用例這是我手工完成的。

Answer 1

我認爲這裏的問題是DFS拓撲排序算法只能保證產生有效的拓撲排序，而不是字典順序的第一種拓撲排序（這是你需要的）。

您可能會修復此問題的一種方法是更改​​您用於執行拓撲排序的算法。考慮使用另一種標準算法，該算法通過維護一組所有具有indegree 0的節點，然後重複刪除一個並使用indegree 0更新節點集合，而不是使用DFS。如果使用優先級隊列來選擇節點indegree 0並且在每次迭代中具有最低的數值，您將得到滿足由該問題給出的約束的拓撲排序。

希望這會有所幫助！

Answer 2

這裏是一個輸入，打破你的程序：

4 4 
2 4 
4 1 
3 1 

答案應該是2 3 4 1，但你的代碼打印3 2 4 1

的原因是，您所訪問的頂點在索引順序中;然而，更高階的索引可能導致索引節點較低。

這個問題應該有一個簡單的O（m + nlogn）解決方案，但我看不出如何輕鬆修復您的代碼。你知道這段代碼是自寫的以來最好的，所以祝你好運。

Answer 3

dfs算法在此特定問題中超時。藉助一些聰明的技巧，您可以將解決方案的複雜性提高到O（m）。您需要消除您正在使用的排序順序對所有邊進行排序。我保留了一個反向邊的列表，即對於兩個邊u-> v和w-> v，我最初將它們添加到列表li [v] - > u-> w中。然後遍歷從1到n，我創建了糾正的有向邊，但這次他們出來自動按順序排列。

無論如何這個時候（對我來說測試case12）。你需要一個非常優化的算法。算法templatetypedef提到工作正常，dfs算法中的dfs遞歸開銷可能有點太多了。

的想法是非常簡單的，你可以看到這個在這裏http://en.wikipedia.org/wiki/Topological_sorting

基本上，你可以用零入度完成的任務，一旦任務完成後，會刪除所有輸出邊沿和更新所有indegrees和找到零度的另一個任務。爲了使事情順利進行，您可以使用優先隊列。

#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; 
}