Cod sursa(job #3209089)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 1 martie 2024 20:40:56
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stdint.h>

const int32_t MAX_N = 50000;

std::vector<int32_t> adj[MAX_N];
bool used[MAX_N];
int32_t sort[MAX_N], top = 0;

void DFS(int32_t vf) {
    used[vf] = true;

    for(int32_t next : adj[vf]) {
        if(!used[next])
            DFS(next);
    }

    sort[top++] = vf;
}

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

    int32_t n, m;
    fin >> n >> m;

    for(int32_t i = 0; i != m; ++i) {
        int32_t x, y;
        fin >> x >> y;
        --x; --y;
        adj[x].push_back(y);
    }

    for(int32_t i = 0; i != n; ++i) {
        if(!used[i])
            DFS(i);
    }

    for(int32_t i = top - 1; i != -1; --i)
        fout << (sort[i] + 1) << ' ';

    fin.close();
    fout.close();

    return 0;
}