Pagini recente » Cod sursa (job #1491084) | Cod sursa (job #3257187) | Cod sursa (job #1734339) | Cod sursa (job #53212) | Cod sursa (job #192823)
Cod sursa(job #192823)
#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;
}