Cod sursa(job #499683)

Utilizator DanutzRusu Dan Andrei Danutz Data 10 noiembrie 2010 17:32:50
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <stdio.h>
struct nod{
	long inf;
	nod *urm;
};
nod *L[50005],*adr;
long n,m,uz[50005];
FILE *f,*g;
void add(long i,long j){
	nod *q;
	q=new nod;
	q->inf=j;
	q->urm=L[i];
	L[i]=q;
}

void cit(){
	f=fopen("sortaret.in","r");
	long i,j,k;
	fscanf(f,"%ld %ld",&n,&m);
	for (k=1;k<=m;k++)
	{ fscanf(f,"%ld %ld",&i,&j);
	  add(i,j);
	}
	fclose(f);
}

void push(long x){
	nod *q;
	q=new nod;
	q->inf=x;
	q->urm=adr;
	adr=q;
}

void df(long k){
	uz[k]=1;
	nod *q;
	for (q=L[k];q;q=q->urm)
	if (uz[q->inf]==0)
		df(q->inf);
	uz[k]=2;
	push(k);
}

void sortare(){
	long i;
	for (i=1;i<=n;i++)
		if (uz[i]==0)
			df(i);
}

void afis(){
	g=fopen("sortaret.out","w");
	nod *q;
	for (q=adr;q;q=q->urm)
		fprintf(g,"%ld ",q->inf);
	fclose(g);
}

int main(){
	cit();
	sortare();
	afis();
	return 0;
}