Cod sursa(job #799494)

Utilizator raluca_vacaruVacaru Raluca-Ioana raluca_vacaru Data 19 octombrie 2012 09:07:04
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <cstdio>
#define MAXN 50001
#define MAXM 100001

using namespace std;

struct node {
    int inf;
    node* nxt;
};

node* v[MAXN];
int n, m, nr, ok[MAXN], po[MAXN];

/* void init () {
    int i;
    for (i=1; i<=n; ++i)
        v[i]->nxt = NULL;
}  */

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

void read () {
    //freopen ("sortaret.in", "r", stdin);
    //printf ("asdfg");
    //scanf ("%d%d", &n, &m);
    ifstream f ("sortaret.in");
    f>>n>>m;
    int i, x, y;
    //printf ("asdfgh");
    for (i=1; i<=m; ++i) {
        //scanf ("%d%d", &x, &y);
        f>>x>>y;
        push (x, y);
    }
    f.close ();
}

void dfs (int x) {
    node* p;
    p = v[x]->nxt;
    ok[x] = 1;
    while (p != NULL) {
        if (ok[p->inf] == 0)
            dfs (p->inf);
        p = p->nxt;
    }
    po[++nr] = x;
}

void topsort () {
    for (int i=1; i<=n; ++i)
        if (ok[i] == 0)
            dfs (i);
}

void write () {
    freopen ("sortaret.out", "w", stdout);
    int i;
    for (i=n; i>0; --i) {
        printf ("%d ", po[i]);
    }
}

int main () {
    read ();
  //  init ();
    topsort ();
    write ();
    return 0;
}