Cod sursa(job #193145)

Utilizator stefysStefan stefys Data 2 iunie 2008 16:49:05
Problema Parcurgere DFS - componente conexe Scor 10
Compilator c Status done
Runda Arhiva educationala Marime 1.63 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXNODURI 100000
#define DEFAULTALLOC 32

void insert(unsigned int src, unsigned int dest, unsigned int *graf[MAXNODURI], unsigned int *allocated, unsigned int *size)
{
	if (!allocated[src]) {
		allocated[src] = DEFAULTALLOC;
		graf[src] = malloc(sizeof(unsigned int) * allocated[src]);
	} else if (size[src] >= allocated[src]) {
		allocated[src] <<= 1;
		graf[src] = realloc(graf[src], sizeof(unsigned int) * allocated[src]);
	}
	
	graf[src][ size[src]++ ] = dest;
	
	if (src < dest) insert(dest, src, graf, allocated, size);
}

void DFS (unsigned int *graf[MAXNODURI], unsigned int visited[MAXNODURI], unsigned int size[MAXNODURI], unsigned int src)
{
	unsigned int i;
	visited[src] = 1;
	for (i=0; i<size[src]; ++i)
		if (!visited[graf[src][i]])
			DFS(graf, visited, size, graf[src][i]);
}

int main (void)
{
	unsigned int *graf[MAXNODURI], size[MAXNODURI], visited[MAXNODURI], allocated[MAXNODURI], nrNoduri, nrMuchii, i;
	unsigned int src, dest, componente=0;
	
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w+", stdout);
	
	scanf("%u %u\n", &nrNoduri, &nrMuchii);
	
	memset(size, 0, sizeof(unsigned int) * nrNoduri);
	memset(visited, 0, sizeof(unsigned int) * nrNoduri);
	memset(allocated, 0, sizeof(unsigned int) * nrNoduri);
	
	for (i=0; i<nrMuchii; ++i) {
		scanf("%u %u\n", &src, &dest);
		insert(src-1, dest-1, graf, allocated, size);
	}
	
	for (i=0; i<nrNoduri; ++i)
		if (!visited[i]) {
			DFS(graf, visited, size, i);
			++componente;
		}
		
	printf("%u\n", componente);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}