Cod sursa(job #1641104)

Utilizator StanescuVictorStanescu Victor Laurentiu StanescuVictor Data 8 martie 2016 20:57:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
// Infoarena DFS

#include <fstream>
#include <vector>
#include <stack>

std::vector<std::vector<int>> graph;
std::vector<bool> visited;
int vertices, edges;

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

	std::stack<int> stack;

	stack.push(vertex);
	visited[vertex] = true;

	while (!stack.empty())
	{
		int index, element = stack.top();
		bool found = false;

		for (index = 0; index < graph[element].size() && !found; index++)
			if (!visited[graph[element][index]])
				found = true;

		if (found)
		{
			index--;
			stack.push(graph[element][index]);
			visited[graph[element][index]] = true;
		}
		else
			stack.pop();
	}
}

int main()
{
	std::ifstream f("dfs.in");
	f >> vertices >> edges;
	graph.resize(vertices);
	visited.resize(vertices, false);

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

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

	std::ofstream g("dfs.out");
	g << c;
	return 0;
}