Cod sursa(job #343026)

Utilizator aghamatMorariu Razvan aghamat Data 24 august 2009 17:25:24
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <stdio.h>
#define DIM 100000

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

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


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

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