Cod sursa(job #288427)

Utilizator adrianraduleaRadulea Adrian adrianradulea Data 25 martie 2009 19:44:11
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<stdio.h>
long vf,t[4][200000],viz[50000],n,m,liber,i,grad[50000],c[50000],x,y,p;
FILE *f,*g;
void df(long k)
{ long pp; if(!viz[k]) fprintf(g,"%ld ",k); viz[k]=1;
  pp=c[k];
  while(pp!=0) { if(!viz[t[1][pp]]) df(t[1][pp]); pp=t[2][pp]; }
}
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++; }
   }
  for(i=1;i<=n;i++) if(grad[i]==0) vf=i;
  df(vf);
  fclose(g);
  return 0;
}