Cod sursa(job #540424)

Utilizator devill_08Buli.vlad devill_08 Data 23 februarie 2011 22:51:27
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <stdio.h>

long a[10000][10000],c[100000],viz[100000];
long i,k,n,m,x,y;

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

void bf (long a[10000][10000], long n, long x)
{
	long p,u,v;
	c[1]=x; viz[x]=1;
	p=u=1;
	while(p<=u)
	{
		v=c[p++];
		for(i=1;i<=n;i++)
			if(a[v][i]==1 && viz[i]==0)
			{
				c[++u]=i;
				viz[i]=1;
			}
	}
}

void comp_conexe ()
{
	long i;
	for(i=1;i<=n;++i) viz[i]=0;
	x=1;
	do
	{
		k++;
		bf(a,n,x);
		x=1;
		while(viz[x]==1 && x<=n) x++;
	}while(x<=n);
}
	

int main ()
{

	citire ();
	comp_conexe ();
	printf("%ld", k);
	return 0;
}