Cod sursa(job #1259925)

Utilizator felixiPuscasu Felix felixi Data 10 noiembrie 2014 18:23:20
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

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

const int NMAX = 50000;

vector <int> sol;
vector <int> d[NMAX+1];

int parent[NMAX+1];
bool viz[NMAX+1];
int N,M;

void citire() {
    in >> N >> M;
    for( int i= 1;  i<=M;  ++i ) {
        int x,y;
        in >> x >> y;
        d[x].push_back(y);
        parent[y]++;
    }
}

void Make_sol() {
    queue<int> q;
    for( int i= 1;  i<=N;  ++i ) {
        if( !parent[i] ) {
            q.push( i );
        }
    }
    while( !q.empty() ) {
        int aux= q.front();
        q.pop();
        viz[aux]= 1;
        out << aux << ' ';
        for( int i= 0;  i<(int)d[aux].size();  ++i ) {
            int nod= d[aux][i];
            --parent[ nod ];
            if( !parent[ nod ] )  q.push(nod);
        }
    }
}



int main() {
    citire();
    Make_sol();
    return 0;
}