Cod sursa(job #289902)

Utilizator tibiletsKoos Tiberiu Iosif tibilets Data 27 martie 2009 09:52:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include<fstream.h>
struct nod
 {int inf;
  nod *adr;
 };
nod *a[50001],*p;
void ad(nod *&l,int n)
{nod* p;
 p=new nod;
 p->inf=n;
 p->adr=l;
 l=p;}
int i,x,y,n,m,gr[50001],s[50001];//complexitate O(N+M)
int main()
{ifstream f("sortaret.in");
ofstream g("sortaret.out");
f>>n>>m;
for(i=1;i<=n;++i)a[i]=0;
for(;m;--m)
{f>>x>>y;
 ++gr[y];
 ad(a[x],y);}
for(x=1;x<=n;++x)
 if(!gr[x]) s[++s[0]]=x;
for(i=1;i<=n;++i)
{p=a[s[i]];
 while(p)
 {y=p->inf;
  --gr[y];
  if(!gr[y]) s[++s[0]]=y;
  p=p->adr;
 }
}
for(i=1;i<=n;++i)
 g<<s[i]<<' ';
return 0;
}