Cod sursa(job #281991)

Utilizator andreea_mandreea martinovici andreea_m Data 16 martie 2009 18:06:55
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<stdio.h>
#define N 100000

int n,m;
bool viz[N];
struct nod
{
	int info;
	nod *adr;
};
nod *v[N];

void adauga(nod *&vf,int x)
{
	nod *q=new nod;
	q->info=x;
	q->adr=vf;
	vf=q;
}
	
void citire()
{
	int x,y;
	scanf("%d%d", &n, &m);
	while(m--)
	{
		scanf("%d%d", &x, &y);
		adauga(v[x],y);//adauga y in lista vecinilor lui x
		adauga(v[y],x);
	}
}
/*
void afisare(nod *p)
{
	while(p)
	{
		printf("%d ",p->info);
		p=p->adr;
	}
	printf("\n");
}
*/
void dfs(int x)
{
	int y;
	nod *aux=v[x];
	viz[x]=true;
	while(aux)
	{	
		y=aux->info;
		if(!viz[y])
			dfs(y);
		aux=aux->adr;
	}
}

int main()
{
	int nr=0;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	citire();
	for(int i=1;i<=n;i++)
		afisare(v[i]);
	for(int i=1;i<=n;i++)
	{
		if(!viz[i])
		{
			dfs(i);
			nr++;
		}
	}
	printf("%d",nr);
	return 0;
}