Cod sursa(job #547199)

Utilizator tiriplicamihaiTiriplica Mihai Dragos tiriplicamihai Data 5 martie 2011 23:21:34
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>

#define MaxN 50010

struct nod{
	long long inf;
	nod *urm;}*L[MaxN],*c;
	
long long M,N,x,y,i;

int s[MaxN];

void insert(long long x,long long y)
{
	nod *q=new nod;
	if(!L[x])
	{
		q->inf=y;
		L[x]=q;
		L[x]->urm=0;
	}
	else
	{
		q->inf=y;
		q->urm=L[x];
		L[x]=q;
	}
}

void cit()
{
	long long i;
	scanf("%lld %lld",&N,&M);
	for(i=1;i<=M;i++)
	{
		scanf("%lld %lld",&x,&y);
		insert(x,y);
	}
}

void insertc(long long k)
{
	nod *q=new nod;
	q->inf=k;
	q->urm=c;
	c=q;
}

void dfs(int k)
{
	nod *q=new nod;
	s[k]=1;
	for(q=L[k];q;q=q->urm)
		if(!s[q->inf])
			dfs(q->inf);
	insertc(k);
}
	
void afis()
{
	nod *q=new nod;
	for(q=c;q;q=q->urm)
		printf("%lld ",q->inf);
}

int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	cit();
	for(i=1;i<=N;i++)
		if(!s[i])
			dfs(i);
	afis();
	printf("\n");
	fclose(stdin);
	fclose(stdout);
	return 0;
}