Cod sursa(job #1666253)

Utilizator FernandoSandoiu Fernando Fernando Data 27 martie 2016 20:28:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

int m, n;
int i, j;
vector< vector<int> > graph;
vector<bool> visited;

void dfs(int vertex){

	if (vertex<0 || vertex>n - 1){
		return;
	}
	stack<int> s;
	int element;
	bool found;
	s.push(vertex);
	visited[vertex] = true;
	while (!s.empty()){
		element = s.top();
		found = false;
		for (i = 0; i<graph[element].size() && !found; i++){
			if (!visited[graph[element][i]]){
				found = true;
			}
		}
		if (found){
			i--;
			s.push(graph[element][i]);
			visited[graph[element][i]] = true;
		}
		else{
			s.pop();
		}
	}


}

int main()
{
	ifstream fin("dfs.in");
	ofstream fout("dfs.out");
	fin >> n >> m;
	graph.resize(n);
	visited.resize(n, false);
	int x, y;
	for (int i = 0; i<m; i++){
		fin >> x >> y;
		x--;
		y--;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	int count = 0;
	for (int i = 0; i<visited.size() && i<n; i++){
		if (!visited[i]){
			dfs(i);
			count++;
		}
	}
	fout << count;
	fin.close();
	fout.close();
	return 0;
}