Cod sursa(job #1015524)

Utilizator alex.glontGlontaru Alexandru alex.glont Data 24 octombrie 2013 19:57:27
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

fstream in ( "sortaret.in" , ios::in ),
        out( "sortaret.out", ios::out);

vector <int> ad[50000];
queue <int> q;
int n, m, nrs[50001];


void citire(){

    int x, y;

    for(int i=0; i<m; i++){

        in >> x >> y;
        ad[x].push_back( y );
        nrs[y]++;
    }

}

void parcurgere(){

    int x, y;

    for(int i=1; i<=n; i++){

        if( !nrs[i] ){

            q.push(i);
        }
    }

    while(!q.empty()){
        x=q.front();
        q.pop();
        while(!ad[x].empty()){

            y=ad[x].back();
            ad[x].pop_back();
            nrs[y]--;
            if(!nrs[y]) q.push(y);
        }
        out<<x<<' ';
    }

}

int main(){

    in >> n >> m;

    citire();
    parcurgere();

    return 0;

}