Cod sursa(job #380958)

Utilizator raica_cristiraica dumitru cristian raica_cristi Data 8 ianuarie 2010 11:44:21
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<stdio.h>
#define dim 101000

struct nod
{
    int el;
    nod *next;
} *liste[dim],*q;
int c[dim],st,dr;
int n,m,s;
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",&x,&y);
        add(x,y);
        i[y]++;
    }
}
void addc(int x)
{ 
     ++dr;
     c[dr]=x;
     printf("%d ",x);
}

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);
        p=p->next;
    }
}
void solve()
{
    for(int k=1;k<=n;k++)
        if(!i[k])
        addc(k),addq(k);
        while(st<=dr)
        {
            scan(c[st]);
            //printf("%d ",c[st]);
            st++;
            s++;
        }
}
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();
// /afis();
return 0;

}