Cod sursa(job #559253)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 17 martie 2011 18:37:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <algorithm>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

const char Input[] = "sortaret.in";
const char Output[] = "sortaret.out";

const int Dim = 50001;

int N, M;
int gr[Dim];
queue <int> q;
vector <int> v[Dim];

int main() {

    ifstream fin( Input );
    ofstream fout( Output );

    int i, x, y, nod;
    vector <int> :: iterator it;

    fin >> N >> M;
    while( M-- ) {

        fin >> x >> y;
        v[x].push_back( y );
        ++gr[y];
    }

    for( i = 1; i <= N; ++i )
        if( !gr[i] )
            q.push( i );

    while( !q.empty() ) {

        nod = q.front();
        q.pop();
        fout << nod << " ";

        for( it = v[nod].begin(); it != v[nod].end(); ++it ) {

            --gr[*it];
            if( !gr[*it] )
                q.push( *it );
        }
    }

    fin.close();
    fout.close();

    return 0;
}