Cod sursa(job #147744)

Utilizator cnatlLaurian cnatl Data 3 martie 2008 14:30:03
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<stdio.h>
struct nod{long int inf;nod *next;};
nod *prim, *ultim, *pr, *lv[100],*p;
long int x,y,n,m,i,grin[100];
void punev(long int a, long int b);
void punec(nod* &prim,nod* &ultim,long int a);
int main()
{   FILE *f=fopen("sortaret.in","r"),
         *g=fopen("sortaret.out","w");
    fscanf(f,"%ld%ld",&n,&m);
    for(i=1;i<=m;i++)
    {  fscanf(f,"%ld%ld",&x,&y);
       punev(x,y); grin[y]++;
     }

    prim=ultim=0;
    for(i=1;i<=n;i++) if(!grin[i]) punec(prim,ultim,i);
    pr=prim;
    while(prim<=ultim)
    { p=lv[prim->inf];
      while(p){ grin[p->inf]--;
                if(grin[p->inf]==0) punec(prim,ultim,p->inf);
                if(p->next==NULL)break;
                p=p->next;
                }
      prim=prim->next;
      }

     while(pr){ fprintf(g,"%ld ",pr->inf);
                pr=pr->next;
                }
     fcloseall();
     return 0;

}
void punev(long int  a, long int b)
{
   nod *q;
   q=new nod; q->inf=b;
   if(!lv[a]){ lv[a]=q;lv[a]->next=0; return;}
   q->next=lv[a];
   lv[a]=q;
}
void punec(nod* &prim, nod* &ultim,long int a)
{  nod *q;
   q=new nod; q->inf=a;
   if(!prim){ prim=ultim=q; return;}
   ultim->next=q;
   ultim=q;
}