Cod sursa(job #192823)

Utilizator stefysStefan stefys Data 31 mai 2008 17:31:04
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.27 kb
#include <stdio.h>
#include <stdlib.h>

int main (void)
{
	unsigned int **graf, size[50000], grad_out[50000], sortat[50000], alloced[50000];
	unsigned int nrNodes, nrEdges, i, src, dest, sortat_size=0, j, k;
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w+", stdout);
	scanf("%u %u\n", &nrNodes, &nrEdges);
	graf = malloc(sizeof(*graf) * nrNodes);
	memset(size, 0, sizeof(unsigned int) * nrNodes);
	memset(grad_out, 0, sizeof(unsigned int) * nrNodes);
	memset(alloced, 0, sizeof(unsigned int) * nrNodes);

	for (i=0; i<nrEdges; ++i) {
		scanf("%u %u\n", &src, &dest);
		--src; --dest;
		if (!alloced[src]) { alloced[src] = 32; graf[src] = malloc(sizeof(unsigned int)*alloced[src]); }
		else if (size[src] >= alloced[src]) {
			alloced[src] <<= 1;
			graf[src] = realloc(graf[src], sizeof(unsigned int)*alloced[src]);
		}
		graf[src][ size[src]++ ] = dest;
		++grad_out[dest];
	}
	
	for (i=0; i<nrNodes; ++i)
		if (!grad_out[i]) sortat[sortat_size++] = i;
	for (i=0; i<nrNodes; ++i) {
		for (j=0; j<size[sortat[i]]; ++j) {
			k = graf[sortat[i]][j];
			--grad_out[k];
			if (!grad_out[k]) sortat[sortat_size++] = k;
		}
	}
	for (i=0; i<nrNodes; ++i)
		printf("%u ", sortat[i]+1);
	printf("\n");
	fclose(stdin);
	fclose(stdout);
	return 0;
}