Cod sursa(job #1561455)

Utilizator alexandru92alexandru alexandru92 Data 4 ianuarie 2016 08:34:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <array>
#include <vector>
#include <stack>
#include <iterator>
#include <algorithm>

const int NMAX = 50011;
std::stack<int> rTopSort;
std::array<bool, NMAX> vWas;
std::array<std::vector<int>, NMAX> G;

void dfs(int x) {
    if (vWas[x]) return;

    vWas[x] = true;
    for (const int& y: G[x]) {
        if (!vWas[y]) {
            dfs(y);
        }
    }
    rTopSort.push(x);
}

int main() {
    int N, M, x, y;
    std::ifstream in{"sortaret.in"};
    std::ofstream out{"sortaret.out"};

    in >> N >> M;
    while(M--) {
        in >> x >> y;
        G[x].push_back(y);
    }

    for (int i = 1; i <= N; ++i) {
        if (!vWas[i]) {
            dfs(i);
        }
    }

    for (; !rTopSort.empty(); rTopSort.pop()) {
        out << rTopSort.top() << ' ';
    }
    out << '\n';

    return 0;
}