Cod sursa(job #289883)

Utilizator tibiletsKoos Tiberiu Iosif tibilets Data 27 martie 2009 09:28:46
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.42 kb
#include<fstream.h>
int i,x,y,n,m,gr[50001],s[50001],a[50001][100001];//complexitate O(N+M)
int main()
{ifstream f("sortaret.in");
ofstream g("sortaret.out");
f>>n>>m;
for(;m;--m)
 f>>x>>y,++gr[y],a[x][++a[x][0]]=y;
for(x=1;x<=n;++x)
 if(!gr[x]) s[++s[0]]=x;
for(i=1;i<=n;++i)
{x=s[i];
 for(m=1;m<=a[x][0];++m)
 {y=a[x][m];
  --gr[y];
  if(!gr[y]) s[++s[0]]=y;
 }
}
for(i=1;i<=n;++i)
 g<<s[i]<<' ';
return 0;
}