Cod sursa(job #799507)

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

using namespace std;

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

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

void init () {
    int i;
    for (i=1; i<=n; ++i)
        {
            v[i]=new node;
            v[i]=NULL;
        }
}

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

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

void dfs (int x) {
    node* p;
    p = v[x];
    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=1; i<=n; ++i) {
        printf ("%d ", po[i]);
    }
}

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