Cod sursa(job #191661)

Utilizator stefysStefan stefys Data 27 mai 2008 20:28:59
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>
#include <stdlib.h>

int main (void)
{
	unsigned int **graf, *size, *grad_out, *sortat;
	unsigned int nrNodes, nrEdges, i, src, dest, sortat_size=0, j, k;
	freopen("sortaret.in", "r", stdin);
	freopen("sortare.out", "w+", stdout);
	scanf("%u %u\n", &nrNodes, &nrEdges);
	graf = malloc(sizeof(*graf) * nrNodes);
	size = malloc(sizeof(unsigned int) * nrNodes);
	sortat = malloc(sizeof(unsigned int) * nrNodes);
	grad_out = malloc(sizeof(unsigned int) * nrNodes);
	memset(size, 0, sizeof(unsigned int)*nrNodes);
	for (i=0; i<nrNodes; ++i) graf[i] = malloc(sizeof(**graf) * nrEdges);
	
	for (i=0; i<nrEdges; ++i) {
		scanf("%u %u\n", &src, &dest);
		--src; --dest;
		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) {
			--grad_out[j];
			if (!grad_out[j]) sortat[sortat_size++] = j;
		}
	}
	for (i=0; i<nrNodes; ++i) {
		printf("%u ", sortat[i]);
	}
	printf("\n");
	fclose(stdin);
	fclose(stdout);
	return 0;
}