Cod sursa(job #773391)

Utilizator gicu_01porcescu gicu gicu_01 Data 1 august 2012 16:49:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 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;
}