Cod sursa(job #423232)

Utilizator piroslPiros Lucian pirosl Data 23 martie 2010 17:28:01
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <stdio.h>


struct node
{
	int value;
	node *link;
};


node* nodes[100001];
int v[100001];


void cleanup(node *n)
{
	if(n == NULL)
		return;
	cleanup(n->link);
	delete n;
}


void dfs(int i, int c)
{
	v[i] = c;
	node* t = nodes[i];
	while(t != NULL) 
	{
		if(v[t->value] == 0) 
		{
			dfs(t->value, c);
		}
		t = t->link;
	}
}


int main(void)
{
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);


	int n, m;
	int c = 1;
	int i;

	scanf("%d %d", &n, &m);

	for(i=0;i<n;++i)
	{
		nodes[i] = NULL;
		v[i] = 0;
	}

	for(i=0;i<m;++i)
	{
		int a,b;
		scanf("%d %d", &a, &b);
		node* n1 = new node;
		n1->value = b;
		n1->link = nodes[a];
		nodes[a] = n1;
		node* n2 = new node;
		n2->value = a;
		n2->link = nodes[b];
		nodes[b] = n2;
	}


	for(i=0;i<n;++i)
	{
		if(v[i] == 0)
		{
			dfs(i, c);
			c++;
		}
	}

	for(i=0;i<n;++i)
	{
		cleanup(nodes[i]);
	}

	printf("%d\n",c-1);

	return 0;
}