Cod sursa(job #153236)

Utilizator butyGeorge Butnaru buty Data 10 martie 2008 12:19:02
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<stdio.h>
const int Nmax=50001;
struct lista
{
	int inf;
    lista *urm;
};
int N,M,Timp;
int T[Nmax],V[Nmax],Ord[Nmax];
lista *G[Nmax];
void cit()
{
	int i,a,b;
    lista *C[Nmax];
	freopen("sortaret.in","r",stdin);
	scanf("%d%d",&N,&M);
	for(i=1;i<=N;i++)
	{
		G[i]=new lista;
		G[i]->urm=NULL;
		C[i]=G[i];
	}
	for(i=1;i<=M;i++)
	{
		scanf("%d%d",&a,&b);
		C[a]->urm=new lista;
		C[a]=C[a]->urm;
		C[a]->inf=b;
		C[a]->urm=NULL;
	}
}

void df_timpifinali(int k)
{
	T[k]=Timp--;
	lista *c;
	for(c=G[k]->urm;c;c=c->urm)
		if(V[c->inf]==0)
			df_timpifinali(c->inf);
}
void sorttop()
{
	Timp=N;
	df_timpifinali(1);
	int i;
	for(i=1;i<=N;i++)
		Ord[N-T[i]+1]=i;
}
void scr()
{
	freopen("sortaret.out","w",stdout);
	int i;
	for(i=1;i<=N;i++)
		printf("%d ",Ord[i]);
	printf("\n");
	fclose(stdout);
}
int main()
{
	cit();
	sorttop();
	scr();
	return 0;
}