Cod sursa(job #2610521)

Utilizator DevilOnFieldTudor Horia Niculescu DevilOnField Data 4 mai 2020 23:03:31
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include<stdio.h>
#include<vector>

using namespace std;

const int MAXN = 50001;

vector <int> g[MAXN], sol;
bool viz[MAXN];
FILE *in, *out;

void topo(int n) {
    if(viz[n]) {
        return;
    }
    viz[n] = true;

    for(auto &it : g[n]) {
        topo(it);
    }

    sol.push_back(n);
}




int main () {
    in = fopen("sortaret.in", "r");
    out = fopen("sortaret.out", "w");

    int n, m;
    fscanf(in, "%d %d", &n, &m);

    for(int i = 0; i < m; i++) {
        int x, y;
        fscanf(in, "%d %d", &x, &y);
        g[x].push_back(y);
    }

    fclose(in);

    for(int i = 1; i <= n; i++) {
        topo(i);
    }

    for(auto i = sol.rbegin(); i != sol.rend(); i++) {
        fprintf(out, "%d ", *i);
    }

    fclose(out);

    return 0;
}