Pagini recente » Cod sursa (job #2139892) | Monitorul de evaluare | Cod sursa (job #741668) | Cod sursa (job #1138502) | Cod sursa (job #191676)
Cod sursa(job #191676)
#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, 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(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[i]) { alloced[i] = 1; graf[i] = malloc(sizeof(unsigned int)); }
else if (size[src] >= alloced[i]) {
alloced[i] <<= 1;
graf[i] = realloc(graf[i], sizeof(unsigned int)*alloced[i]);
}
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;
}