Cod sursa(job #645434)

Utilizator belginstirbuasdf asdf belginstirbu Data 9 decembrie 2011 16:56:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.22 kb
#include <stdio.h>
#include <stdlib.h>

#define NEW(x) (x*)malloc(sizeof(x))

struct NODE
{
	int info;
	struct NODE *next;
} **list;

unsigned int N, M, contComp = 0;
short *viz;

void add(struct NODE **root, unsigned int x)
{
	struct NODE *temp;
	if(!root)
	{
		*root = NEW(struct NODE);
		(*root) -> next = NULL;
		(*root) -> info = x;
	}
	else
	{
		temp = NEW(struct NODE);
		temp -> info = x;
		temp -> next = *root;
		*root = temp;
	}
}

void DFS(unsigned int x)
{
	struct NODE *iter;

	viz[x] = 1;
	for(iter = list[x]; iter; iter = iter -> next)
		if(!viz[iter -> info])
		{
			viz[iter -> info] = 1;
			DFS(iter -> info);
		}
}

int main()
{
	unsigned int i = 0;
	unsigned int x, y;
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);

	scanf("%u %u", &N, &M);

	viz = (short*)malloc(sizeof(short) * (N + 1));
	list = (struct NODE**)malloc(sizeof(struct NODE*) * (N + 1));

	for(i = 1; i <= N; ++i)
	{
		viz[i] = 0;
		list[i] = NULL;
	}

	for(i = 0; i < M; ++i)
	{
		scanf("%u %u", &x, &y);
		add(&list[x], y);
		add(&list[y], x);
	}

	for(i = 1; i <= N; ++i)
		if(!viz[i])
		{
			++contComp;
			DFS(i);
		}

	printf("%u", contComp);

	return 0;
}