Cod sursa(job #631950)

Utilizator StefanLacheStefan Lache StefanLache Data 9 noiembrie 2011 22:34:23
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.47 kb

#include<stdio.h>
int N,M,A[1000][1000],s[1000],nr;
void constr()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&N,&M);
	int i,a,b;
	for(i=1;i<=M;i++)
	{
		scanf("%d%d",&a,&b);
		A[a][b]=A[b][a]=1;
	}
}
void DFS(int nod)
{
	int i;
	s[nod]=1;
	for(i=1;i<=N;i++)
		if(A[nod][i]==1&&s[i]==0)
			DFS(i);
}
int main()
{
	constr();int i;
	for(i=1;i<=N;i++)
		if(!s[i])
		{nr++;DFS(i);}
	printf("%d",nr);
	return 0;
}