Cod sursa(job #2458243)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 19 septembrie 2019 22:49:49
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;

vector<vector<size_t> > graph(50001, vector<size_t>());
size_t M, N;
vector<size_t> sol;
size_t deg[50001];

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

    fin >> N >> M;

    size_t x, y;

    for(size_t i = 1; i <= M; ++i)
    {
        fin >> x >> y;
        graph.at(x).push_back(y);
        deg[y]++;
    }

    sol.push_back(0);

    for(size_t i = 1; i <= N; ++i)
        if(deg[i] == 0) sol.push_back(i);

    for(size_t i = 1; i <= N; i++)
        for(size_t j = 0; j < graph.at(sol.at(i)).size(); ++j)
            if(--deg[graph.at(sol.at(i)).at(j)] == 0) sol.push_back(graph.at(sol.at(i)).at(j));

    for(size_t i = 1; i <= N; ++i) fout << sol.at(i) << " ";
}