Cod sursa(job #1426183)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 29 aprilie 2015 06:23:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

void dfs(const vector<vector<int> >& adiacente, const int s, vector<bool>& gasit){
	gasit[s] = true;
	stack<int> de_viz;
	de_viz.push(s);
	int cur;
	while(!de_viz.empty()){
		cur = de_viz.top();
		de_viz.pop();
		for(auto next : adiacente[cur]){
			if(!gasit[next]){
				de_viz.push(next);
				gasit[next] = true; } } } }

int main(){
	ifstream f("dfs.in");
	ofstream g("dfs.out");
	int n, m;
	f >> n >> m;
	vector<vector<int> > adiacente(n);
	for(int i = 0, a, b; i < m; ++i){
		f >> a >> b;
		--a, --b;
		adiacente[a].push_back(b);
		adiacente[b].push_back(a); }
	vector<bool> gasit(n, false);
	int rez = 0;
	for(int i = 0; i < n; ++i){
		if(!gasit[i]){
			++rez;
			dfs(adiacente, i, gasit); } }
	g << rez;
	return 0; }