Cod sursa(job #191817)

Utilizator stefysStefan stefys Data 28 mai 2008 17:36:27
Problema Parcurgere DFS - componente conexe Scor 5
Compilator c Status done
Runda Arhiva educationala Marime 1.51 kb
#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] = 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]);
		}
		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;
}