Cod sursa(job #273323)

Utilizator BloodRainBurceanu Gabriel BloodRain Data 8 martie 2009 14:21:29
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<fstream.h>
ifstream in("sortaret.in");
ofstream out("sortaret.out");
int x,y,n,i,m;
int *d;
int *rasp;
int* a[50003];
int viz[50003],st[50003],vf=1;
int main(void)
{
in>>n>>m;
d=new int[n+1];
rasp=new int[n+1];
for(i=1;i<=n;i++)
	d[i]=0;
for(i=1;i<=m;i++)
	{
	in>>x>>y;
	d[x]++;
	}
in.close();
for(i=1;i<=n;i++)
	{
	a[i]=new int[d[i]+1];
	a[i][0]=d[i];
	}
ifstream inn("sortaret.in");
inn>>n>>m;
for(i=1;i<=m;i++)
	{
	inn>>x>>y;
	a[x][a[x][0]]=y;
	a[x][0]--;
	}
inn.close();

int p;

int numar=1;
for(int z=1;z<=n;z++)
{
if(viz[z]==0)
{
vf=1;
st[vf]=z;
viz[z]=1;
while(vf>0)
{
p=0;
for(int j=1;j<=d[st[vf]];j++)
	{
	if(viz[a[st[vf]][j]]==0)
		{
		st[vf+1]=a[st[vf]][j];
		viz[a[st[vf]][j]]=1;
		vf++;
		p=1;
		}
	}
if(p==0)
	{
	rasp[numar]=st[vf];
	numar++;
	vf--;
	}
}
}
}
for(i=n;i>0;i--)
	out<<rasp[i]<<" ";
out<<"\n";

out.close();
return 0;
}