Cod sursa(job #289701)

Utilizator adrianraduleaRadulea Adrian adrianradulea Data 26 martie 2009 22:01:17
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<stdio.h>
long vf,t[4][200001],viz[50001],n,j,m,liber,i,grad[50001],c[50001],x,y,p,ok,ind,d[50001],k;
FILE *f,*g;
int main()
{ f=fopen("sortaret.in","r"); g=fopen("sortaret.out","w");
  fscanf(f,"%ld%ld",&n,&m);
  liber=1;
  for(i=1;i<=m;i++)
   { fscanf(f,"%ld%ld",&x,&y); grad[y]++;
     if(c[x]==0) { c[x]=liber; t[1][liber]=y; liber++; }
     else
      { p=c[x];
	while(t[2][p]!=0) p=t[2][p];
	t[2][p]=liber;
	t[1][liber]=y;
	liber++;
      }
   }
  ok=1;
  while(ok)
   { k=0; ind=0;
     for(i=1;i<=n;i++) if(grad[i]<=0)
      { if(grad[i]==0) { fprintf(g,"%ld ",i); k++; d[k]=i; grad[i]=-1;} ind++; }
     for(i=1;i<=k;i++)
      { p=c[d[i]];
	while(t[2][p]!=0)
	 { grad[t[1][p]]--;
	   p=t[2][p];
	 }
	grad[t[1][p]]--; c[d[i]]=0;
      }
     if(ind==n) ok=0;
   }
  fclose(g);
  return 0;
}