Cod sursa(job #686301)

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

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

// declar lista de adiacenta pt grafuri
set<int> liste;
vector<set<int> > graf(100001, liste);

// 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;
	
	// micsorez numarul de componente ale grafului
	graf.resize(N+1);
	
	// 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].insert(b);
		
		// graful este neorientat
		graf[b].insert(a);
	}
	fin.close();
}

void dfs(int nod) {
	// marchez nodul curent ca vizitat
	VIZ[nod] = true;
	
	// parcurg nodurile grafului
	for(int i=1; i<=N; i++) {
		// daca nodul nu a fost vizitat si exista legatura de la nod la i
		if(!VIZ[i] && graf[nod].find(i) != graf[nod].end()) {	// asa se verifica daca exista un element intr-o multime 	
			// il vizitez
			dfs(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();
}