Cod sursa(job #466829)

Utilizator whoasdas dasdas who Data 27 iunie 2010 17:07:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
using namespace std;

struct elem
{
	long inf;
	elem* next;
	elem(long _inf)
	{
		inf = _inf;
		next=NULL;
	}
};
void adauga(elem* &rad, long inf)
{
	if(rad==NULL)
		rad=new elem(inf);
	else
	{
		elem* temp =new elem(inf);
		temp->next=rad;
		rad=temp;
	}
}

long n,m;
elem *lista;
elem *lad[50001];
bool viz[500001];
long grad[500001];

void df(long nod)
{
	viz[nod]=true;
	
	for(elem *i=lad[nod];i;i=i->next)
		if(viz[i->inf]==false)
			df(i->inf);

	adauga(lista,nod);
}
int main()
{
	long i,j,a,b;
	
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%ld%ld",&n,&m);
	for(i=1;i<=n;i++)
	{
		lad[i]=NULL;
		viz[i]=false;
		grad[i]=0;
	}
	for(i=1;i<=m;i++)
	{
		scanf("%ld%ld",&a,&b);
		adauga(lad[a],b);
		grad[b]++;
	}
	for(i=1;i<=n;i++)
		if(grad[i]==0)
			df(i);
	for(;lista;lista=lista->next)
		printf("%ld ",lista->inf);
	

	return 0;
}