Cod sursa(job #1641064)

Utilizator StanescuVictorStanescu Victor Laurentiu StanescuVictor Data 8 martie 2016 20:43:50
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
// Infoarena DFS

#include <fstream>
#include <vector>
#include <stack>
typedef unsigned int uint;

std::vector<std::vector<uint>> graph;
uint vertices, edges;

void read()
{
	std::ifstream f("dfs.in");
	f >> vertices >> edges;
	graph.resize(n);

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

std::vector<uint> depthFirstSearch(uint vertex)
{
	if (!isValidVertex(vertex))
		return std::vector<uint>();

	std::vector<bool> visited(vertices);
	std::stack<uint> stack;
	std::vector<uint> connectedComponent;

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

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

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

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

	return connectedComponent;
}

std::vector<std::vector<uint>> getConnectedComponents()
{
	std::vector<std::vector<uint>> connectedComponents;
	std::vector<bool> visited(vertices, false);

	for (uint i = 0; i < vertices; i++)
	{
		if (!visited[i])
		{
			connectedComponents.push_back(depthFirstSearch(i));

			for (uint j = 0; j < connectedComponents.back().size(); j++)
				visited[connectedComponents.back()[j]] = true;
		}
	}

	return connectedComponents;
}

int main()
{
	read(n, m, graph);
	std::vector<std::vector<uint>> cC = getConnectedComponents();
	std::ofstream g("dfs.out");
	g << cC.size();
	return 0;
}