Cod sursa(job #194820)

Utilizator stefysStefan stefys Data 14 iunie 2008 16:25:21
Problema Parcurgere DFS - componente conexe Scor 10
Compilator c Status done
Runda Arhiva educationala Marime 1.74 kb
#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;
}