Cod sursa(job #281986)

Utilizator andreea_mandreea martinovici andreea_m Data 16 martie 2009 17:12:55
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include<stdio.h>
#define N 1001
int n,m,a[N][N],k=0;
bool viz[N];
void citire()
{
	int x,y;
	scanf("%d%d", &n, &m);
	while(m--)
	{
		scanf("%d%d", &x, &y);
		a[x][++a[x][0]]=y;
		a[y][++a[y][0]]=x;
	}
}

void dfs(int x)
{
	int y;
	viz[x]=true;
	for(int i=1;i<=a[x][0];i++)
	{
		y=a[x][i];
		if(!viz[y])
			dfs(y);
	}
}

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