Cod sursa(job #191670)

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

int main (void)
{
	unsigned int **graf, size[50000], grad_out[50000], sortat[50000];
	unsigned int nrNodes, nrEdges, i, src, dest, sortat_size=0, j, k, readoffset;
	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(graf, 0, sizeof(*graf) * nrNodes);
	
	readoffset = ftell(stdin);
	
	for (i=0; i<nrNodes; ++i) {
		scanf("%u %u\n", &src, &dest);
		++size[src-1]; ++size[dest-1];
	}
	for (i=0; i<nrNodes; ++i)
		graf[i] = malloc(sizeof(**graf) * size[i]);
	memset(size, 0, sizeof(unsigned int) * nrNodes);

	fseek(stdin, readoffset, SEEK_SET);
	
	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) {
			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;
}