Cod sursa(job #191830)

Utilizator stefysStefan stefys Data 28 mai 2008 20:08:22
Problema Parcurgere DFS - componente conexe Scor 35
Compilator c Status done
Runda Arhiva educationala Marime 1.88 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.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; /* will implement a bitset later */
	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]);
		}
		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 {
		*(queue_push++) = nod;
		while (queue_push-queue_pop > 0) {
			crt = *(queue_pop++);
			visited[crt] = 1;
			for (i=0; i<size[crt]; ++i)
				if (!visited[graf[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;
}