Cod sursa(job #493054)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 16 octombrie 2010 21:16:29
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
//latime

#include<stdio.h>
#include<string.h>

#define Nmax 1001

char G[Nmax][Nmax], viz[Nmax];

int coada[Nmax], N, M;

void latime(int nod) {
	int j, st=1, dr=1;
	coada[st]=nod; viz[nod]=1;
	while(st<=dr) {
		nod=coada[st];
		for(j=1; j<=N; j++)
			if(!viz[j] && G[nod][j]==1) {
				coada[++dr]=j;
				viz[j]=1;
		}
		//printf("%d ",coada[st++]);
	}
	//printf("\n");
}

int main() {
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	
	int i, j, cnt=0;
	scanf("%d %d",&N,&M);
	while(M--) {
		scanf("%d %d",&i,&j);
		G[i][j]=G[j][i]=1;
	}
	
	for(i=1; i<=N; i++) 
		if(!viz[i])
			latime(i),
			++cnt;
	
	printf("%d\n",cnt);
	return 0;
}