Pagini recente » Cod sursa (job #1531694) | Monitorul de evaluare | Istoria paginii utilizator/floarea_raul | Cod sursa (job #1317177) | Cod sursa (job #191776)
Cod sursa(job #191776)
#include <stdio.h>
#include <stdlib.h>
int main (void)
{
unsigned int nrNoduri, nrMuchii, i, j, **graf, src, dest, *alloced, *size;
unsigned int *queue, *queue_push, *queue_pop, crt, nod=0, componente=0;
char *visited;
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w+", stdout);
scanf("%u %u\n", &nrNoduri, &nrMuchii);
graf = malloc(sizeof(*graf) * nrNoduri);
alloced = malloc(sizeof(unsigned int) * nrNoduri);
size = malloc(sizeof(unsigned int) * nrNoduri);
visited = malloc(sizeof(char) * nrNoduri);
queue = queue_push = queue_pop = malloc(sizeof(unsigned int) * nrNoduri);
memset(alloced, 0, sizeof(unsigned int) * nrNoduri);
memset(size, 0, sizeof(unsigned int) * nrNoduri);
memset(visited, 0, sizeof(char) * nrNoduri);
for (i=0; i<nrMuchii; ++i) {
scanf("%u %u\n", &src, &dest);
--src; --dest;
if (!alloced[src]) { alloced[src] = 1; graf[i] = malloc(sizeof(**graf)); }
else if (size[src] >= alloced[src]) {
alloced[src] <<= 1;
graf[src] = realloc(graf[src], sizeof(**graf) * alloced[src]);
}
graf[src] [ size[src]++ ] = dest;
}
do {
*(queue_push++) = nod;
while (queue_push-queue_pop > 0) {
crt = *(queue_pop++);
visited[crt] = 1;
for (i=0; i<size[crt]; ++i) *(queue_push++) = graf[crt][i];
}
for (nod=0; nod<nrNoduri && visited[nod]; ++nod);
++componente;
queue_push = queue_pop = queue;
} while (nod < nrNoduri);
printf("%u\n", componente);
fclose(stdin);
fclose(stdout);
return 0;
}