Cod sursa(job #1609739)

Utilizator bragaRObragaRO bragaRO Data 22 februarie 2016 23:10:37
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb

#include <iostream>
#include <cstdlib>
#include <vector>
#include <stack>
#include <fstream>

using namespace std;

int m, n;

vector <vector <int> > graph;
vector <bool> visited;
ifstream f("dfs.in");
ofstream h("dfs.out");
int nr_conexe = 0;

void dfs(int vertex)
{
	if (vertex<0 || vertex>n - 1) return;

	stack <int> s;
	int element, i;
	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)
		{
			int k = i - 1;
			s.push(graph[element][k]);
			visited[graph[element][k]] = true;
		}
		else s.pop(); 
		

	}

}


int main()
{
	int x, y, i;
	f >> n >> m;
	graph.resize(n);
	visited.resize(n, false);

	for (i = 0; i<m; i++)
	{
		f >> x >> y;
		x--; y--;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}

	
	for (i = 0; i<visited.size(); i++)
		if (!visited[i]) { dfs(i);nr_conexe++; }
		
	h << nr_conexe;

	f.close();
	h.close();
	return 0;
}