Cod sursa(job #1713867)

Utilizator S4lexandruAlexandru Stefanica S4lexandru Data 6 iunie 2016 20:18:59
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stack>
#include <array>
#include <vector>
#include <fstream>


const int NMAX = 50011;
using neighbours=std::vector<int>;
using graph=std::array<neighbours, NMAX>;

graph G;
std::array<bool, NMAX> visited;
std::stack<int> topologicalSort;

void dfs(int v) {
    visited[v] = true;

    for (const auto& x: G[v]) {
        if (!visited[x]) {
            dfs(x);
        }
    }
    topologicalSort.push(v);
}

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

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

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

    while (!topologicalSort.empty()) {
        out << topologicalSort.top() << ' ';
        topologicalSort.pop();
    }


    in.close();
    out.close();
    return 0;
}