Cod sursa(job #686330)

Utilizator mateiuliIulian mateiuli Data 21 februarie 2012 16:12:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
//#include <iostream>
#include <vector>
#include <set>
using namespace std;

// N noduri, M muchii
int N, M;

// declar matricea
vector<int> graf[100001];

// multime de noduri nevizitate - daca exista e vizitat
bool VIZ[100001];

// functii interne
void citire();
void dfs();
void rez();

int main() {
	citire();
	rez();
}

void citire() {
	ifstream fin("dfs.in");
	fin>>N>>M;
	
	// citesc muchiile
	int a, b;
	for(int i=1; i<=M; i++) {
		// citesc valorile
		fin>>a>>b;
		
		// adaug nodului a, nodul b in lista de adiacenta
		graf[a].push_back(b);
		
		// graful este neorientat
		graf[b].push_back(a);
	}
	fin.close();
}

void dfs(int nod) {
	// marchez nodul curent ca vizitat
	VIZ[nod] = true;
	
	// parcurg vecinii nodului nod
	for(int i = 0; i < graf[nod].size(); i++) {
		// daca nodul nu a fost
		if(!VIZ[graf[nod][i]]) {
			// il vizitez
			dfs(graf[nod][i]);
		}
	}
}

void rez() {
	// ca sa verific cate componente conexe are un graf
	// il parcurg prin DFS pornind din fiecare nod
	// si daca la fiecare parcurgere gasesc un nod nevizitat, 
	// atunci am gasit o comp conexa
	int compConexe = 0;
	for(int i=1; i<=N; i++) {
		if(!VIZ[i]) {
			compConexe++;
			dfs(i);	
		}			
	}
	
	// afisez rezultatul
	ofstream fout("dfs.out");
	fout<<compConexe;
	fout.close();
}