Cod sursa(job #493195)

Utilizator cdascaluDascalu Cristian cdascalu Data 17 octombrie 2010 14:43:03
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include<stdio.h>
#define MAX 100000
int x,u;
int a[MAX][MAX],cont,ind,car[MAX],nr;
void df(int i)
{
	int j;
	for(j=1;j<=x;++j)
	if(a[j][i] && !car[j])
	{
		a[j][i] = 0;
		a[i][j] = 0;
		car[j] = 1;
		df(j);
	}
}
int main()
{
	FILE*f = fopen("dfs.in","r");
	int i,x1,y1;
	fscanf(f,"%d %d",&x,&u);
	for(i=1;i<=u;++i)
	{
	    fscanf(f,"%d%d",&x1,&y1);
	    a[x1][y1] = 1;
	    a[y1][x1] = 1;
	}
	fclose(f);
	for(i=1;i<=x;++i)
	if(!car[i])
		{
			car[i] = 1;
			df(i);
			++nr;
		}
	printf("%d ",nr);
	return 0;
}