Cod sursa(job #477287)

Utilizator barneystinsonBarney barneystinson Data 14 august 2010 02:47:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <cstdio>
#include <vector>
#define N_MAX 100005
using namespace std;
FILE*f=fopen("dfs.in","r");
FILE*g=fopen("dfs.out","w");

int N,M;
char viz[N_MAX];
vector <int> graf[N_MAX];

void dfs(int tata){
	for(int i =0;i<graf[tata].size();i++){
		if(!viz[graf[tata][i]]){
			viz[graf[tata][i]]=1;
			dfs(graf[tata][i]);
		}
	}
}

int main(){
	
	fscanf(f,"%d %d",&N,&M);
	int nod1,nod2,i,j;
	for(i=1;i<=M;i++){
		fscanf(f,"%d %d",&nod1,&nod2);
		graf[nod1].push_back(nod2);
		graf[nod2].push_back(nod1);
	}
	int compconexe=0;
	for(i=1;i<=N;i++){
		if(!viz[i]){
			viz[i]=1;
			compconexe++;
			dfs(i);
		}
	}
	
	fprintf(g,"%d",compconexe);
	
	fclose(f);
	fclose(g);
	return 0;
}