Cod sursa(job #289173)

Utilizator alexandru92alexandru alexandru92 Data 26 martie 2009 15:20:28
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<stdio.h>
#include<stdlib.h>
#define Nmax 50001
struct nod
     {
      int varf;
      nod *urm;
     };
nod *L[Nmax];
inline void Insert(int x,int y)
     {
      nod *q=(nod *)calloc(1,sizeof(nod));
      q->varf=y;
      q->urm=L[x];
      L[x]=q;
     }
int main()
  {int n,m,i,u=0,p,x,y;
   int *grde,*v;
   freopen("sortaret.in","rt",stdin);
   freopen("sortaret.out","wt",stdout);
   scanf("%d %d",&n,&m);
   grde=(int *)calloc(n+1,sizeof(n));
   v=(int *)calloc(n+1,sizeof(n));
   for(i=1;i<=m;++i)
      {scanf("%d %d",&x,&y);
       Insert(x,y); grde[y]++;
      }
   for(i=1;i<=n;++i)
      if(grde[i]==0) v[++u]=i;
   for(i=1;i<=n;++i)
	{
	 x=v[i];
	 for(nod *p=L[x];p;p=p->urm)
	    {grde[p->varf]--;
	     if(!grde[p->varf]) v[++u]=p->varf;
	    }
	 }
   for(i=1;i<=n;++i) printf("%d ",v[i]),free(L[i]);
   free(v); free(grde);
   return 0;
  }