Cod sursa(job #380648)

Utilizator raica_cristiraica dumitru cristian raica_cristi Data 7 ianuarie 2010 09:48:48
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include<stdio.h>

#define dim 101000

struct nod 
{
       int el;
       nod *next ;
} *liste[dim], *c;

int n,m,k,x,y;
int i[dim];
int viz[dim];

void add(int x,int y)
{
     nod *p=new nod;
     p->el=y;
     p->next=liste[x];
     liste[x]=p;
}
void read()
{
     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 el)
{ 
              i[el]=-1;
              nod *t=new nod;
              t->el=el;
              t->next=c;
              c=t;

}
void del()
{
     for(int i=1;i<=n;i++)
     viz[i]=0;
 }
void bf(int l)
{
     viz[l]=1;
     nod *p=new nod;
     for(p=liste[l]  ;p ; p=p->next)
     if(!viz[p->el])
     {
                    if(i[p->el]>0)
                    {
                    i[p->el]--;
                    bf(p->el);
                    if(i[p->el]==0)
                        addc(p->el);
                    }
}
}
void solve()
{
     nod *t=new nod;
     for(int k=1;k<=n;k++)
     {
             if(i[k]==0)
             {
                        i[k]=-1;
                                t->el=k;
                                t->next=c;
                                c=t;
                                del();
                               bf(k);
                                }
             
             }
 }
void afis()
{
     while(c)
     {
             printf("%d ",c->el);
             c=c->next;
             }
 }
void afis1()
{
     nod *p=new nod;
     for(int i=1;i<=n;i++)
     {
             p=liste[i];
             while(p)
             {
                     printf("%d ",p->el);
                     p=p->next;
                     }
             printf("\n");
             }
 }
int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
   // printf("plm"); 
    read();
    solve();
    afis(); 
    return 0;
}