Cod sursa(job #315373)

Utilizator hasegandaniHasegan Daniel hasegandani Data 15 mai 2009 10:26:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<stdio.h>

#define nmax 50001

struct nod
{
    int vf;
    nod *urm;
} *l[nmax],*push;

int n,m,viz[nmax];

void add(nod *&inc,int info)
{
    nod *p=new nod;
    p->vf=info;
    p->urm=inc;
    inc=p;
}
void DF(int i)
{
    viz[i]=1;
    for(nod *t=l[i];t;t=t->urm)
        if (viz[t->vf]==0)
            DF(t->vf);
    viz[i]=2;
    add(push,i);
}

void read()
{
    int a,b;
    freopen("sortaret.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
        {
        scanf("%d%d",&a,&b);
        add(l[a],b);
        }
}

void afis()
{
    freopen("sortaret.out","w",stdout);
    for(nod *t=push;t;t=t->urm)
        printf("%d ",t->vf);
    printf("\n");
}

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

int main()
{
    read();
    s_topologica();
    afis();
    return 0;
}