Pagini recente » Cod sursa (job #1004609) | Cod sursa (job #1208734) | Cod sursa (job #2352196) | Cod sursa (job #351246) | Cod sursa (job #194820)
Cod sursa(job #194820)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXNODURI 100000
int main (void)
{
unsigned int nrNoduri, nrMuchii, i, *graf[MAXNODURI], src, dest, alloced[MAXNODURI], size[MAXNODURI];
unsigned int stack[MAXNODURI], *stack_push, crt, nod=0, componente=0;
char visited[MAXNODURI];
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w+", stdout);
scanf("%u %u\n", &nrNoduri, &nrMuchii);
stack_push = stack;
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;
/*dynamically growing arrays */
if (!alloced[src]) { alloced[src] = 32; graf[src] = malloc(sizeof(**graf)*alloced[src]); }
else if (size[src] >= alloced[src]) {
alloced[src] <<= 1;
graf[src] = realloc(graf[src], sizeof(**graf) * alloced[src]);
}
if (!alloced[dest]) { alloced[dest] = 32; graf[dest] = malloc(sizeof(**graf)*alloced[dest]); }
else if (size[dest] >= alloced[dest]) {
alloced[dest] <<= 1;
graf[dest] = realloc(graf[dest], sizeof(**graf) * alloced[dest]);
}
/***********************/
graf[src] [ size[src]++ ] = dest;
graf[dest] [ size[dest]++ ] = src;
}
do {
*(stack_push++) = nod;
visited[nod] = 1;
while (stack_push > stack) {
crt = *(stack_push--);
for (i=0; i<size[crt]; ++i)
if (!visited[graf[crt][i]]) {
*(stack_push++) = graf[crt][i];
visited[graf[crt][i]] = 1;
}
}
for (++nod; nod<nrNoduri && visited[nod]; ++nod);
++componente;
stack_push = stack;
} while (nod < nrNoduri);
printf("%u\n", componente);
fclose(stdin);
fclose(stdout);
return 0;
}