Cod sursa(job #1154327)

Utilizator roxana.istratePoenaru Roxana roxana.istrate Data 26 martie 2014 09:26:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <stack>
#include <vector>

#define MAX  100000

using namespace std;

int vect[MAX];
vector<vector<int>> adiacenta;

void dfs(int v){
	
	stack<int> s;
	s.push(v);

	while(!s.empty()){
		int x = s.top();
		s.pop();
		for(int i = 0; i < adiacenta[x].size(); i++){
			int elem = adiacenta[x].at(i);
			if(!vect[elem]){ vect[elem] = 1; s.push(elem); }
		}
	}

}


int main(){
	ifstream fin("dfs.in");
	ofstream fout("dfs.out");
	
	int n, m, a, b, count = 0;
	
	fin >> n >> m;

	vector<int> v;
	for(int i = 0; i < n; i++){
		adiacenta.push_back(v);
	}

	for(int i = 0; i < m; i++){
		fin >> a >> b;
		adiacenta[--a].push_back(--b);
		adiacenta[b].push_back(a);
	}


	for(int i = 0; i < n ; i++){
		if(!vect[i]){
			dfs(i);
			count++;
		}
	}
	fout << count << "\n";
	return 0;
}