Cod sursa(job #2331094)

Utilizator Valentin0709Datcu George Valentin Valentin0709 Data 29 ianuarie 2019 10:26:45
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <stdio.h>
using namespace std;

#define NMAX 50005

FILE * f = fopen("sortaret.in", "r");
FILE * g = fopen("sortaret.out", "w");

int n, m, k, i, viz[NMAX], sol[NMAX];

struct nod {
    int inf;
    nod* urm;
} *l[NMAX];

void adaug_nod(nod* &l, int x) {
    nod* p = new nod;

    p->inf = x;
    p->urm = l;
    l = p;
}

void citire() {
    int x, y;

    fscanf(f, "%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        fscanf(f, "%d%d", &x, &y);
        adaug_nod(l[x], y);
    }
}

void df(int i) {
    nod *p;

    viz[i] = 1;
    for(p = l[i]; p != NULL; p = p->urm)
        if(!viz[p->inf]) df(p->inf);
    sol[++k] = i;
}

int main() {

    citire();

    for(i = 1; i <= n; i++)
        if(!viz[i]) df(i);

    for(i = n; i >= 1; i--) fprintf(g, "%d ", sol[i]);

    fclose(f); fclose(g);

    return 0;
}