Cod sursa(job #884468)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 20 februarie 2013 22:35:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <vector>
#include <list>
#include <queue>

int main(){
    std::ifstream fin("sortaret.in");
    std::ofstream fout("sortaret.out");

    unsigned N,M; fin>>N>>M;
    std::vector<std::list<unsigned> > adjlists(N);
    std::vector<unsigned> graduri(N,0);
    while(M--){unsigned x,y;fin>>x>>y;graduri[y-1]++;adjlists[x-1].push_back(y-1);}

    std::queue<unsigned> sor;
    for(unsigned i=0;i<N;++i) if(graduri[i]==0) sor.push(i);

    while(!sor.empty()){
        fout<<sor.front()+1<<' ';
        for(std::list<unsigned>::iterator i=adjlists[sor.front()].begin();
                                          i!=adjlists[sor.front()].end();++i){
            graduri[*i]--;
            if(graduri[*i]==0) sor.push(*i);
        }
        sor.pop();
    }
}