Cod sursa(job #295461)

Utilizator razvan_3dragomir razvan razvan_3 Data 3 aprilie 2009 12:16:30
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<fstream.h>
ifstream intrare("sortaret.in");
ofstream iesire("sortaret.out");
unsigned int muchie[100001][2];
long start[50001];
unsigned int ramasi[50001];
unsigned int loc;
unsigned sol[50001];
unsigned int n
long int m;
void citeste()
{
	intrare>>n>>m;
	long int x,y,count=1;
	for(long int i=1;i<=m;i++)
	{
		intrare>>x>>y;
		muchie[count][0]=y;
		muchie[count][1]=start[x];
		start[x]=count;
		count++;
		ramasi[y]++;
	}
}
void back(int k)
{
	unsigned int nod=muchie[k][0];
	if(nod!=0)
	{
		ramasi[nod]--;
		if(ramasi[nod]==0)
		{
			loc++;
			sol[loc]=nod;
			back(start[nod]);
		}
	   //	else ramasi[nod]--;
		if(muchie[k][1]!=0)back(muchie[k][1]);
	}
}
int main()
{
	citeste();
	for(unsigned int i=1;i<=n;i++)
	{
		if(ramasi[i]==0)
		{
			loc++;
			sol[loc]=i;
			back(start[i]);
		}
	}
	for(unsigned int j=1;j<=n;j++)
	{
		iesire<<sol[j]<<" ";
	}
	return 0;
}