Cod sursa(job #530194)

Utilizator blastoiseZ.Z.Daniel blastoise Data 7 februarie 2011 10:00:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <stdio.h>
#include <string.h>

int N,M,x,y,i,sol,use[100002];

struct tree
{
	int nod;
	tree *link;
}*Graf[100002];

inline void add(int x,int y)
{
	tree *p;

	p=new tree;
	p->nod=y;
	p->link=Graf[x];
	Graf[x]=p;
}

inline void df(int nod)
{
	tree *p=Graf[nod];

	use[nod]=1;
	while(p)
	{
		if(!use[p->nod]) df(p->nod);
		p=p->link;
	}
}

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

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

	for(i=1;i<=M;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}

	memset(use,0,sizeof(use));

	sol=0;

	for(i=1;i<=N;i++)
		if(!use[i])
		{
			df(i);
			sol++;
		}

	printf("%d\n",sol);

	return 0;
}