Cod sursa(job #380819)

Utilizator raica_cristiraica dumitru cristian raica_cristi Data 7 ianuarie 2010 20:55:55
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<stdio.h>
#define dim 101000

struct nod
{
    int el;
    nod *next;
} *liste[dim],*c,*q;
int n,m;
int i[dim];
void add(int x,int y)
{
    nod *p=new nod;
    p->el=y;
    p->next=liste[x];
    liste[x]=p;
}
void read()
{
    int x,y;
    scanf("%d %d\n",&n,&m);
    for(int k=1;k<=m;k++)
    {
        scanf("%d %d\n",&y,&x);
        add(x,y);
        i[y]++;
    }
}
void addc(int x)
{
    nod *p=new nod;
    p->el=x;
    p->next=c;
    c=p;
}

void addq(int x)
{
    nod *p=new nod;
    p->el=x;
    p->next=q;
    q=p;
}
void scan(int x)
{
    nod *p=liste[x];
    while(p)
    {
        i[p->el]--;
        if(i[p->el]==0)
        addc(p->el),addq(p->el);
    }
}
void solve()
{
    for(int k=1;k<=n;k++)
        if(i[k]==0)
        addc(k),addq(k);
        while(c)
        {
            scan(c->el);
            c=c->next;
        }
}
void afis()
{
    while(q)
    {
        printf("%d ",q->el);
        q=q->next;
    }
}
int main ()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    read();
    solve();
return 0;

}