Cod sursa(job #296199)

Utilizator HaggisRanca Razvan Haggis Data 4 aprilie 2009 14:01:44
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<fstream>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
struct nod{int inf; nod*leg;}*p[50001],*u[50001];
int i,j,n,m,x,y,a[50001],s,k,k1,b[50001];

int main ()
{
in>>n>>m;
for(i=1;i<=m;i++)
{
	in>>x>>y;
	a[y]=1;
	nod*nou=new nod;
	nou->inf=y;
	nou->leg=0;
	if(!p[x])
		p[x]=nou;
	else
		u[x]->leg=nou;
	u[x]=nou;
}
for(i=1;i<=n;i++)
	{
		if(a[i]==0)
			{
				s=i;
				break;
			}
		
	}
b[1]=s;
k=1;
k1=1;
while(b[k])
{
	while(p[b[k]] && p[b[k]]!=u[b[k]])
	{
		b[++k1]=p[b[k]]->inf;
		p[b[k]]=p[b[k]]->leg;
	}
	if(p[b[k]])
		b[++k1]=p[b[k]]->inf;
	a[k]=b[k];
	k++;
}
for(i=1;i<=n;i++)
	out<<a[i]<<" ";

return 0;
}