Cod sursa(job #359666)

Utilizator petroMilut Petronela petro Data 27 octombrie 2009 22:59:49
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<stdio.h>
#define M 1000

FILE *f=fopen("dfs.in","r");
FILE *g=fopen("dfs.out","w");

long n,m;
long viz[M],a[M][M];

void citire()
{
	long i,x,y;
	fscanf(f,"%ld%ld",&n,&m);
	
	for(i=1;i<=m;i++)
		{fscanf(f,"%ld%ld",&x,&y);
	    a[x][y]=a[y][x]=1;
        }
	
	for(i=1;i<=n;i++)
		viz[i]=-1;
	
	fclose(f);
}

void dfs(long nod,long nr)
{
	long i,c[M*10],p,u;
	p=u=1;
	viz[nod]=nr;
	c[p]=nod;
	
	while(p<=u)
	{
		nod=c[p];
		for(i=1;i<=n;i++)
			if(a[nod][i]==1 && viz[i]==-1) {u++;
		                    c[u]=i;
			               viz[i]=nr;}
		
		p++;
	}
}

int main()
{
	citire();
	long nr,i, nod;
	nr=nod=1;
	
	dfs(nod,nr);
	
	int ok=1;
	while(ok)
	{
		ok=0;
		for(i=1;i<=n;i++)
			if(viz[i]==-1) {nr++;
		                    nod=i;
			                ok=1;
			                dfs(nod,nr);} 
	}
	
	fprintf(g,"%ld\n",nr);
	fclose(g);
	return 0;
}