Cod sursa(job #2206677)

Utilizator heisenbugAnnoying Heisenbug heisenbug Data 23 mai 2018 13:11:35
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <queue>
#include <vector>

const size_t MAX_N = 50000 + 1;
const size_t MAX_M = 100000 + 1;

int main()
{
    std::ifstream fin("sortaret.in");
    std::ofstream fout("sortaret.out");

    int N, M;
    fin >> N >> M;

    std::vector<std::vector<int> > graph(N + 1);
    std::vector<int> degrees(N + 1);
    for (int i = 0; i < M; ++i) {
        int x, y;
        fin >> x >> y;
        graph[x].push_back(y);
        ++degrees[y];
    }

    std::queue<int> q;
    for (int i = 1; i <= N; ++i)
        if (degrees[i] == 0)
            q.push(i);

    while (!q.empty()) {
        int top = q.front();
        q.pop();

        fout << top << ' ';
        for (const auto& i : graph[top]) {
            --degrees[i];
            if (degrees[i] == 0)
                q.push(i);
        }
    }

    return 0;
}