Cod sursa(job #144537)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 27 februarie 2008 19:12:28
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<stdio.h>
struct nod{long int info;nod *next;};
nod *prim[50001],*pp;
long int n,m,i,a,b,gr[50001],bottom,top,coada[50001];
void pune();
int main()
{
	FILE *f,*g;f=fopen("sortaret.in","r");g=fopen("sortaret.out","w");
	fscanf(f,"%ld%ld",&n,&m);
	for(i=1;i<=m;i++)
	{ fscanf(f,"%ld%ld",&a,&b);pune();}
	for(i=1;i<=n;i++)
	 if(!gr[i]){top++;coada[top]=i;}
	for(i=1;i<=n;i++)
	{ pp=prim[coada[i]];
	  while(pp)
	  { gr[pp->info]--;
	    if(!gr[pp->info]){top++;coada[top]=pp->info;}
	    pp=pp->next;
	  }
	}
	for(i=1;i<=n;i++)fprintf(g,"%ld ",coada[i]);
	fprintf(g,"\n");
	fcloseall();
	return 0;
}
void pune()
{
	nod *paux;
	gr[b]++;
	paux=new nod;
	paux->info=b;
	if(!prim[a]){paux->next=0;prim[a]=paux;return;}
	paux->next=prim[a];prim[a]=paux;
}