Не могу найти проблему здесь с топологической сортировкой - PullRequest
Новая
       56

Не могу найти проблему здесь с топологической сортировкой

0 голосов
/ 24 февраля 2019

Я только что начал алгоритм графа.Есть код моего алгоритма топологической сортировки с C ++.Это проблема онлайн-судьи UVA.мой вывод не совпадает с принятым выводом .. как будто я даю ввод: -> 8 25 8 6 5 2 7 4 7 1 8 6 6 1 7 1 6 2 8 6 8 6 5 7 6 2 8 4 13 7 1 1 3 6 7 1 3 6 4 2 3 5 2 6 3 8 4 4 3 5 6 0 0

Мой вывод -> 5 8 6 2 7 4 1 3

но принятый результат -> 8 5 6 7 4 2 1 3

, насколько я знаю, топологическая сортировка может иметь разные приемлемые результаты.но я все еще получаю неправильный ответ.

Ссылка на проблему (Упорядочивание задач)

Код: 

#include<bits/stdc++.h>
using namespace std;

void file(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
}

vector<int>graph[102],out;
int n,e,u,v,inDeg[102];

void Back(){
    memset(inDeg,0,sizeof inDeg);
    for(int i=0; i<102; i++)graph[i].clear();
    out.clear();
}

void init(int e){
    for(int i=0; i<e; i++){
        cin>>u>>v;
        graph[u].push_back(v);
        inDeg[v]++;
    }
}

void topoSort(){
    queue<int>q;
    int u;
    for(int i=1; i<=n; i++){
        if(inDeg[i]==0)q.push(i);
    }
    while(!q.empty()){
        u=q.front();
        q.pop();
        out.push_back(u);
        int len=graph[u].size();
        for(int i=0; i<len; i++){
            int v=graph[u][i];
            if(inDeg[v]>0){
                inDeg[v]--;
                if(inDeg[v]==0)q.push(v);
            }
        }
    }
}

void print(){
    int len=out.size();
    for(int i=0; i<len; i++){
        printf("%d ",out[i]);
    }printf("\n");
}

int main(){
    file();
    while(scanf("%d %d",&n,&e) && n!=0 && e!=0){
        init(e);
        topoSort();
        print();
        Back();
    }
return 0;
}

Должен ли я отслеживатьпосещенного узла?

...