Cod sursa(job #650219)

Utilizator EstarDaian Dragos Estar Data 17 decembrie 2011 16:26:12
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fi("sortaret.in");
ofstream fo("sortaret.out");

struct noduri {
    vector<int> next;
    int i , prec;
    noduri(int j){
        i=j;
        prec=0;
    }
};

int main() {
    int n , m,i=0;
    vector<noduri> nod;
    vector<int> coada;
    fi>>n>>m;
    for(int i=0;i<n;i++)
    nod.push_back(noduri(i));
    for(int i=0;i<m;i++){
        int x , y;
        fi>>x>>y;
        nod[x-1].next.push_back(y-1);
        nod[y-1].prec++;
    }
    for(int i=0;i<n;i++){
        if(!nod[i].prec)coada.push_back(i);
    }
    for(;i<(signed)coada.size();i++){
        fo<<coada[i]+1<<' ';
        for(int j=0;j<(signed)nod[coada[i]].next.size();j++){
            nod[nod[coada[i]].next[j]].prec--;
            if(!nod[nod[coada[i]].next[j]].prec){
                coada.push_back(nod[coada[i]].next[j]);
            }
        }
    }
}