Cod sursa(job #153277)

Utilizator butyGeorge Butnaru buty Data 10 martie 2008 12:54:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<stdio.h>
const int Nmax=50001;
struct lista
{
	int inf;
    lista *urm;
};
int N,M,Timp,NR;
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)
{
	
	lista *c;
	V[k]=1;
	for(c=G[k]->urm;c;c=c->urm)
		if(V[c->inf]==0)
		{
			df_timpifinali(c->inf);
		}
	T[++NR]=k;
}
void sorttop()
{
	int i;
	
	for(i=1;i<=N;i++)
			if(V[i]==0)
			{
        df_timpifinali(i);
      }
}
void scr()
{
	freopen("sortaret.out","w",stdout);
	int i;
	for(i=N;i>=1;i--)
		printf("%d ",T[i]);
	printf("\n");
	fclose(stdout);
}
int main()
{
	cit();
	sorttop();
	scr();
	return 0;
}