Cod sursa(job #361026)

Utilizator BaduBadu Badu Badu Data 3 noiembrie 2009 15:10:54
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
//SORTARE TOPOLOGICA

#include<stdio.h>
#include<stdlib.h>
#define MAX 50010

FILE *f=fopen("sortaret.in" ,"rt");
FILE *g=fopen("sortaret.out","wt");

int *A[MAX];
int  V[MAX];
int  P[MAX];
int  n,m,nr;

void date(){

	int x,y,i;
	fscanf(f,"%d%d",&n,&m);
	for( i=1;i<=n;i++){
		A[i]=(int *)realloc(A[i],sizeof(int));
		A[i][0]=0;
	}

	for( i=1;i<=m;i++){
		fscanf(f,"%d%d",&x,&y);
		A[x][0]++;
		A[x]=(int *)realloc(A[x],(A[x][0]+1)*sizeof(int));
		A[x][A[x][0]]=y;
	}
}

void dfs(int nod){
	int i;
	V[i]=1;
	for( i=1;i<=A[nod][0];i++)
		if(!V[A[nod][i]]) dfs(A[nod][i]);

	P[++nr] = nod;
}

int main(){

	int i;
	date();

	for(i=1; i<=n; i++) if(!V[i]) dfs(i);

	for(i=n;i>0;i--) fprintf(g,"%d ",P[i]);

return 0;
}