Cod sursa(job #907796)

Utilizator deresurobertoFMI - Deresu Roberto deresuroberto Data 8 martie 2013 12:39:07
Problema Parcurgere DFS - componente conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<cstdio>
#include<cstring>
struct gr{
	long int nr;
	long int vec[60];
}a[100001];
long int v[100101],viz[100001],n,m,x,y,p,u,k,i,j;

void citire()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++){
	scanf("%ld %ld",&x,&y);
	a[x].nr++;
	a[y].nr++;
	a[x].vec[a[x].nr]=y;
	a[y].vec[a[y].nr]=x;
	}
}

void bf()
{
	memset(v,0,sizeof(v));
	p=1;u=1;
	v[1]=j;
	viz[j]=1;
	while(p<=u){
		for(i=1;i<=a[v[p]].nr;i++)
			if(viz[a[v[p]].vec[i]]==0){
				u++;
				v[u]=a[v[p]].vec[i];
				viz[v[u]]=1;
			}
			p++;
	}
}

int main()
{
	citire();
	for(j=1;j<=n;j++)
		if(viz[j]==0){bf();k++;}
	
	printf("%ld",k);
	return 0;
}