Cod sursa(job #918927)

Utilizator stelutaSfiriac Bianca steluta Data 19 martie 2013 11:18:32
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<cstdio>
using namespace std;

typedef struct Nod {
    int nod;
    Nod *urm;
} NOD;

NOD *p, *v[50005], *lis;
int n, m, a, b, i, viz[50005];

void push(int);
void dfs(int);

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


void push(int x) {
    NOD *p;
    p=new NOD;
    p->nod=x;
    p->urm=lis;
    lis=p;
}

void dfs(int x) {
    NOD *p;
    int t;

    viz[x]=1;
    p=v[x];
    while (p->urm != NULL) {
        t=p->nod;
        if (viz[t]==0) dfs(t);
        p=p->urm;
    }
    push(x);
}

int main () {
    freopen("sortaret.out", "w", stdout);
    freopen("sortaret.in", "r", stdin);
    scanf("%d %d", &n, &m);

    for (i=1; i<=n; ++i) {
        v[i]=new NOD;
        v[i]->nod=50005;
        v[i]->urm=NULL;
    }

    lis=new NOD;
    lis->nod=50005;
    lis->urm=NULL;

    for ( ; m>0; --m) {
        scanf("%d %d", &a, &b);
        p=new NOD;
        p->nod=b;
        p->urm=v[a];
        v[a]=p;
    }

    s_topo();

    p=lis;
    while (p->urm != NULL) {
        printf("%d ", p->nod);
        p=p->urm;
    }

    return 0;
}