Cod sursa(job #296215)

Utilizator HaggisRanca Razvan Haggis Data 4 aprilie 2009 14:20:08
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 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],c[50001];

int main ()
{
in>>n>>m;
for(i=1;i<=m;i++)
{
	in>>x>>y;
	a[y]=1;
	int b=0;
	nod*t=p[x];
	while(t && t!=u[x])
		{
			if(t->inf==y)
				b=1;
			t=t->leg;
		}
	if(t && t->inf==y)
		b=1;
	if(!b)
	{
	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;
c[s]=1;
while(b[k])
{
	while(p[b[k]] && p[b[k]]!=u[b[k]])
	{
		if(!c[p[b[k]]->inf])
			{
				b[++k1]=p[b[k]]->inf;
				p[b[k]]=p[b[k]]->leg;
				c[b[k1]]=1;
			}
	}
	if(p[b[k]])
		{
			b[++k1]=p[b[k]]->inf;
			c[b[k1]]=1;
		}
	a[k]=b[k];
	k++;
}
for(i=1;i<=n;i++)
	out<<a[i]<<" ";

return 0;
}