Cod sursa(job #203092)

Utilizator shade4529Popescu Mihai shade4529 Data 13 august 2008 17:15:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<stdio.h>
FILE *f,*g;
long n,m,nr,i,x,y,c[100005],t[4][200005],viz[100005],deg[100005],v,ok,ok1,elimin[100005];
int main()
{ f=fopen("sortaret.in","r"); g=fopen("sortaret.out","w");
  fscanf(f,"%ld%ld",&n,&m);
  nr=1;
  for(i=1;i<=m;i++)
   { fscanf(f,"%ld%ld",&x,&y);
     if(!c[x])
      { while(t[1][nr]!=0) nr++;
	c[x]=nr;
	t[1][nr]=y; t[3][nr]=x;
	deg[y]++;
      }
     else
      { v=c[x];
	while(t[2][v]!=0) v=t[2][v];
	while(t[1][nr]!=0) nr++;
	t[2][v]=nr; t[1][nr]=y; t[3][nr]=x;
	deg[y]++;
      }
   }
  ok=1; x=0;
  while(ok)
   { x++; ok1=1;
     for(i=1;i<=n;i++) if(deg[i]==0&&!viz[i])
      { fprintf(g,"%ld ",i);
	elimin[i]=x; ok1=0; viz[i]=1;
      }
     if(!ok1)
	for(i=1;i<=nr;i++)
	 if(elimin[t[3][i]]==x)
	  { deg[t[1][i]]--;
	    t[1][i]=0;
	  }
     if(ok1) ok=0;
   }
  fclose(g);
  return 0;
}