Cod sursa(job #2354822)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 25 februarie 2019 16:52:07
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream in("sortaret.in");
ofstream out("sortaret.out");

const int N_MAX = 50000;
const int M_MAX = 100000;

int N, M;
vector<int> Edges[N_MAX + 1];
int postordine[N_MAX + 1], nr;
bool viz[N_MAX + 1];

void DFS(int x) {
    viz[x] = true;
    for(auto y : Edges[x])
        if(!viz[y])
            DFS(y);
    postordine[++nr] = x;
}

int main()
{
    int x, y;
    in >> N >> M;
    for(int i = 1; i <= M; ++i) {
        in >> x >> y;
        Edges[x].push_back(y);
    }

    for(int i = 1; i <= N; ++i)
        if(!viz[i])
            DFS(i);

    for(int i = N; i >= 1; --i)
        out << postordine[i] << ' ';

    return 0;
}