Cod sursa(job #838545)

Utilizator raluca_vacaruVacaru Raluca-Ioana raluca_vacaru Data 19 decembrie 2012 22:11:16
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>
#define MAXN 50001

using namespace std;

struct nod {int inf; nod* urm;};

int n, m;
nod* v[MAXN];

void push (int x, int y) {
    nod* p;
    p = new nod;
    p->inf = y;
    p->urm = v[x];
    v[x] = p;
}

void read () {
    freopen ("sortaret.in", "r", stdin);
    scanf ("%d%d", &n, &m);
    int i, x, y;
    for (i=1; i<=m; ++i) {
        scanf ("%d%d", &x, &y);
        push (x, y);
    }
    fclose (stdin);
}

int nr, postord[MAXN];
bool viz[MAXN];

void DFS (int i) {
    viz[i] = 1;
    nod* p;
    p = v[i];
    while (p) {
        if (!viz[p->inf])
            DFS (p->inf);
        p = p->urm;
    }
    postord[++nr] = i;
}

void sortare () {
    int i;
    for (i=1; i<=n; ++i)
        if (!viz[i]) DFS(i);
}

void write () {
    freopen ("sortaret.out", "w", stdout);
    int i;
    for (i=nr; i>=1; --i)
        printf ("%d ", postord[i]);
    fclose (stdout);
}

int main () {
    read ();
    sortare ();
    write ();
    return 0;
}