Cod sursa(job #487963)

Utilizator szabibibiOrban Szabolcs szabibibi Data 27 septembrie 2010 09:47:07
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.37 kb
#include <stdio.h>


void olvas();
void rendez(long);
void kiir();

typedef long * tomb;
typedef tomb* matrix;
typedef int * tomb2;

const int FEHER = 0;
const int FEKETE = 1;

long n,m;
matrix a;
tomb nek;
tomb sor;
tomb2 szin;
long dick;
long nn;


int main()
{
	int i;
	olvas();
	for (i=1;i<=n;i++)
		if (szin[i]==0) rendez(i);
	kiir();
	for (i=0;i<=n;i++)
	{
		free(a[i]);
		a[i] = NULL;
	}
	free(a);
	a = NULL;
	free(szin);
	free(sor);
	free(nek);
	return 0;
}

void olvas()
{
	long x,y,i;
	FILE *f = fopen("sortaret.in","r");
	
	fscanf(f,"%ld %ld",&n,&m);
	
	a = malloc((n+1) * sizeof(tomb));
	nek = malloc((n+1) * sizeof(long));
	sor = malloc((n+1) * sizeof(long));
	szin = malloc((n+1) * sizeof(int));
	
	for (i=1;i<=n;i++)
	{
		a[i] = malloc (sizeof(long));
		a[i][0] = 0;
		nek[i] = 0;
		szin[i] = 0;
		sor[i] = 0;
	}
	
	for (i=1;i<=m;i++)
	{
		fscanf(f,"%ld %ld",&x,&y);
		nek[x]++;
		nn = nek[x];
		a[x] = (long *) realloc(a[x],(nn+1) * sizeof(long));
		a[x][nn] = y;
	}
	fclose(f);
}

void kiir()
{
	FILE *f = fopen("sortaret.out","w");
	int i;
	for (i=1;i<=n;i++)
		fprintf(f,"%ld ",sor[i]);
	fclose(f);
}


void rendez(long csucs)
{
	int i;
	for (i=1;i<=nek[csucs];i++)
	{
		if (szin[a[csucs][i]] == FEHER) 
			rendez(a[csucs][i]);
	}
	szin[csucs] = FEKETE;
	sor[(n-(++dick))+1] = csucs;
}