Cod sursa(job #771678)

Utilizator harababurelPuscas Sergiu harababurel Data 26 iulie 2012 20:04:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100005
using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

vector <int> vecin[nmax];
bool vizitat[nmax];
int top;

void dfs(int curent) {
	
	vizitat[curent] = true;										//nodul curent marcat ca vizitat
	for(int i = 0; i < int(vecin[curent].size()); i++) {				//ii iau toti vecinii
		if(!vizitat[ vecin[curent][i] ]) dfs(vecin[curent][i]);	//pentru cei nevizitati fac un dfs
	}
}

int main() {
	int n, m, i, a, b, rez=0;
	
	f>>n>>m;
	
	for(i=1; i<=m; i++) {
		f>>a>>b;
		vecin[a].push_back(b);	//graf neorientat
		vecin[b].push_back(a);	//graf neorientat
	}
	
	for(i=1; i<=n; i++) {
		if(!vizitat[i]) {		//incep cu dfs(1), care imi marcheaza ca fiind vizitate toate nodurile
			rez++;				//primei componente conexe. reiau nodurile nevizitate (componente noi)
			dfs(i);				//si fac aceeasi chestie, numarand componentele
		}
	}
	
	g<<rez<<"\n";
	
	f.close();
	g.close();
	return 0;
}