Cod sursa(job #2425423)

Utilizator CristyXtremeSimion Cristian CristyXtreme Data 24 mai 2019 20:05:40
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

vector <vector <int> > v(50001);
vector <int> grad(50001, 0);

void sortaret(int n) {
    queue <int> Q;
    vector <int> d;

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

    while (!Q.empty()) {
        int curent = Q.front();
        Q.pop();

        d.push_back(curent);
        for (auto vecin : v[curent]) {
            grad[vecin]--;
            if (grad[vecin] == 0)
                Q.push(vecin);
        }
    }

    for (int i : d)
        out << i << ' ';
}

int main() {
    int n, m;
    int a, b;

    in >> n >> m;
    for (int i = 0; i < m; i++) {
        in >> a >> b;
        v[a].push_back(b);
        grad[b]++;
    }

    sortaret(n);
    return 0;
}