Cod sursa(job #2628441)

Utilizator doyouhavethetimeStanculescu Gabriel doyouhavethetime Data 15 iunie 2020 23:52:57
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
// minim lexicografic?
#include <bits/stdc++.h>
#define N 50000
using namespace std;

vector <int> G[N+1];
set <int> Q;
array <int, N> depth;
vector <int> ans;

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

    int n, m;
    fin >> n >> m;

    int i, j;
    for (; m; m--) {
        fin >> i >> j;
        G[i].push_back(j);
        ++depth[j];
    }

    for (i=1; i<=n; ++i)
        if (!depth[i])
            Q.insert(i);

    while (!Q.empty()) {
        auto save = *Q.begin();
        Q.erase(Q.begin());
        ans.push_back(save);

        for (auto it: G[save]) {
            --depth[it];
            if (!depth[it])
                Q.insert(it);
        }
    }

    copy(ans.begin(), ans.end(), ostream_iterator <int> (fout, " "));
    return 0;
}