Cod sursa(job #2354763)

Utilizator cristii2000cristiiPanaite Cristian cristii2000cristii Data 25 februarie 2019 16:06:08
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

const int NMAX = 50005;

int n, m;
int grade[NMAX];

vector <int> G[NMAX];
queue <int> Q;

void citire(){
    in >> n >> m;

    for (int i = 0; i < n; ++i) {
        int x, y;
        in >> x >> y;
        G[x].push_back (y);
        grade[y]++;
    }
}

void sortare(){
    for (int i = 1; i <= n; ++i) {
        if(grade[i] == 0){
            Q.push (i);
        }
    }

    while (!Q.empty ()){
        int node = Q.front ();
        Q.pop ();
        out << node << " ";
        for (int i = 0; i < G[node].size (); ++i) {
            int vec = G[node][i];
            grade[vec] --;
            if(grade[vec] == 0)
                Q.push (vec);
        }
    }
}

int main() {

    ios::sync_with_stdio (false);

    citire();
    sortare();
    return 0;
}