Cod sursa(job #478788)

Utilizator a.stanciuStanciu Adrian a.stanciu Data 20 august 2010 13:28:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.47 kb
#include <stdio.h> 
#include <stdlib.h>

#define ALB 1
#define GRI 2
#define NEGRU 3

typedef struct NOD
{
	int val;
	struct NOD *urm;
} Nod;

void init(Nod *list, int n)
{
	int i;
	for (i = 1; i <= n; i++)
		list[i].urm = NULL;
}

void add(Nod *list, int x, int y)
{
	Nod *nod = (Nod *)malloc(sizeof(Nod));
	nod->val = y;

	Nod *tmp = &list[x];
	nod->urm = tmp->urm;
	tmp->urm = nod;
}

void print(Nod *list, int n)
{
	int i;
	Nod *tmp;
	for (i = 1; i <= n; i++)
	{
		printf("%d:", i);
		tmp = &list[i];
		tmp = tmp->urm;
		while (tmp)
		{
			printf("%d ", tmp->val);
			tmp = tmp->urm;
		}
		printf("\n");
	}
}

void parcurgere(Nod *list, int n, int x, int *c)
{
	int v;
	c[x] = GRI;

	Nod *tmp = &list[x];
	tmp = tmp->urm;
	while (tmp)
	{
		v = tmp->val;
		if (c[v] == ALB)
		{
			c[v] = GRI;
			parcurgere(list, n, v, c);
		}
		tmp = tmp->urm;
	}
	c[x] = NEGRU;
}

int dfs(Nod *list, int n)
{
	int i, nr = 0;

	int *c = (int *)malloc(sizeof(int) * (n + 1));
	for (i = 1; i <= n; i++) c[i] = ALB;	

	for (i = 1; i <= n; i++)
		if (c[i] == ALB) 
		{
			nr++;
			parcurgere(list, n, i, c);
		}

	return nr;
}

int main()
{
	int n, m, i, x, y;
	FILE *f, *g;

	f = fopen("dfs.in", "r");
	g = fopen("dfs.out", "w");

	fscanf(f, "%d %d", &n, &m);

	Nod *list = (Nod *)malloc(sizeof(Nod) * (n + 1));
	init(list, n);
	for (i = 0; i < m; i++)
	{
		fscanf(f, "%d %d", &x, &y);
		add(list, x, y);
		add(list, y, x);
	}	

	int nr = dfs(list, n);
	
	fprintf(g, "%d\n", nr);

	fclose(f);
	fclose(g);

	return 0;
}