Cod sursa(job #1182532)

Utilizator petiVass Peter peti Data 6 mai 2014 19:14:08
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <vector>
#include <list>
using namespace std;

int main(){
    ifstream ifs("sortaret.in");
    ofstream ofs("sortaret.out");
    int N,M; ifs>>N>>M;

    vector<list<int> >g(N);
    vector<int> grd(N,0);
    for(int i=0;i<M;i++){
        int x,y;ifs>>x>>y;
        g[--x].push_back(--y);
        grd[y]++;
    }

    list<int> s;
    for(int i=0;i<N;i++)
        if(!grd[i]) s.push_back(i);

    list<int> l;
    while(!s.empty()){
        int b=s.back(); s.pop_back();
        l.push_back(b);
        for(list<int>::iterator it=g[b].begin();it!=g[b].end();it++){
            grd[*it]--;
            if(!grd[*it]) s.push_back(*it);
        }
    }

    for(list<int>::iterator it=l.begin();it!=l.end();it++)
        ofs<<*it+1<<" ";
}