Почему моя логика не работает правильно для 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 до A. Я поддерживаю порядок, сортируя список смежности, который я создал, и сохраняю узлы, которые не имеют каких-либо ограничений отдельно, чтобы печатать их позже в правильном порядке. Используются два массива флагов: один для маркировки обнаруженного узла и один для маркировки узла, чьи соседи были исследованы.

Теперь мое решение - http://www.ideone.com/QCUmKY (важная функция - функция посещения) и его предоставление WA после правильной работы в 10 случаях, поэтому очень трудно понять, где я делаю это неправильно, поскольку он работает для всех тестовых случаев которые я сделал вручную.

Answer 1

Я думаю, что проблема здесь в том, что алгоритм топологической сортировки DFS гарантирован только для получения действительной топологической сортировки, а не для лексикографически первой топологической сортировки (что вам и нужно).

Один из способов, по которым вы могли бы исправить это, - это изменить тот алгоритм, который вы используете для выполнения топологической сортировки. Вместо использования DFS рассмотрите использование другого стандартного алгоритма, который работает, поддерживая набор всех узлов с неопределенным значением 0, затем многократно удаляя один и обновляя набор узлов с неопределенным значением 0. Если вы используете очередь приоритетов для выбора узла с 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, я создал исправленные направленные ребра, но на этот раз они выходят автоматически в порядке.

В любом случае этот раз (на тестовом примере12 для меня). Для этого вам нужен очень оптимизированный алгоритм. Алгоритм 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; 
}