Cod sursa(job #660543)

Utilizator APOCALYPTODragos APOCALYPTO Data 13 ianuarie 2012 07:37:20
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.63 kb
#include<stdio.h>
#include<stdlib.h>
typedef struct nod{
   int f;
   struct nod *next;
} nod;

nod *G[10000];
int t[10000];
int N,M;
nod* qp, *qu;
nod* insert(nod *prim,int y)
{
    nod *p;

    p=(nod*) malloc(sizeof(nod*));
    p->f=y;
    if(prim==NULL)
    {
       //prim=p;
       p->next=NULL;
       prim=p;
    }
    else
    {
        p->next=prim;
        prim=p;
    }
    return prim;
}

void push(nod **prim, nod **ultim,int x)
{
    nod *p;
    p=(nod*) malloc(sizeof(nod*));
    p->f=x;
    if((*prim)==NULL)
    {
         p->next=NULL;
         (*prim)=p;
         (*ultim)=p;
    }
    else
    {
        (*ultim)->next=p;
        p->next=NULL;
        (*ultim)=p;
    }

}

void pop(nod **prim, nod** ultim)
{
    nod *p=(*prim);
    (*prim)=(*prim)->next;
    free(p);
}

void cit()
{
    int i,x,y;
    scanf("%d %d",&N,&M);
    //printf("init rau\n");
    for(i=1;i<=N;i++)
        G[i]=NULL;
    //printf("init bun\n");
    for(i=1;i<=M;i++)
    {
        scanf("%d %d",&x,&y);
        G[x]=insert(G[x],y);
        t[y]++;

    }
    //printf("graf bun\n");
    qp=NULL;
    qp=qu;
    for(i=1;i<=N;i++)
    {
        if(t[i]==0)
        {
            push(&qp,&qu,i);
        }
    }
}

void solve()
{
    int u;
    nod* p;
    while(qp!=NULL)
    {
        u=qp->f;
        pop(&qp,&qu);
        for(p=G[u];p!=NULL;p=p->next)
        {
            t[p->f]--;
            if(t[p->f]==0)
            {
                push(&qp,&qu,p->f);
            }
        }
        printf("%d ",u);
    }

    printf("\n");
}

int main()
{
    freopen("sortret.in","r",stdin);
    freopen("sortret.out","w",stdout);
    cit();
    solve();
    return 0;
}