Cod sursa(job #3248507)

Utilizator ioanabaduIoana Badu ioanabadu Data 12 octombrie 2024 09:25:55
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#define N_MAX 50005
#include <vector>

using namespace std;

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

vector <int> graph[50005];
int nodes, arcs, num;
bool viz[N_MAX];
int postorder[N_MAX];

void dfs (int x){
    viz[x] = true;

    for (auto idx:graph[x])
        if (!viz[idx])
            dfs(idx);
    postorder[++num] = x;
}

int main (){
    int x, y;

    in >> nodes >> arcs;
    for (int i=1; i<=arcs; i++){
        in >> x >> y;

        graph[x].push_back(y);
    }

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

    for (int i=nodes; i>0; --i){
        out << postorder[i] << ' ';
    }

    return 0;
}