Cod sursa(job #343064)

Utilizator aghamatMorariu Razvan aghamat Data 24 august 2009 21:04:13
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <stdio.h>
#define DIM 100005

struct Nod{
			int x;
			Nod *adr;} *pNod;
pNod *lst[DIM];
int n,m,a,b,vizitat[DIM];

void add(int a, int b)
{
	pNod p
	p=new(Nod);
	p->adr=lst[a];
	p->x=b;
	lst[a]=p;
}


void df(int nod)
{
	pNod p;
	vizitat[nod]=1;
	for (p=lst[i]; p; p=p->adr)
		if (!vizitat[p->x]0)
			df(p->x);
}

int main()
{   int i,j;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&n,&m);
	int val=0;
	for (i=1; i<=n; ++i)
		{
			scanf("%d%d",&a,&b);
			add(a,b);
			add(b,a);
		}
	for(i=1; i<=n; ++i)
	  if (!vizitat[i])
	   {
		val++;
		df(i);
	   }
	printf("%d\n",val);
	return 0;
}