Cod sursa(job #779229)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 17 august 2012 02:35:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb

#include <fstream>
#include <vector>
#include <list>
#include <utility>
#include <stack>

typedef std::list<unsigned int> edge;
typedef std::vector<edge> graph;

unsigned int DepthFirstSearch (graph &g)
{
	std::stack<unsigned int> stack;
	edge::const_iterator iterator, stop;
	std::vector<bool> visited(g.size(),false);
	unsigned int components(0), neighbor;
	for (unsigned int node(1), end(visited.size()) ; node < end ; ++node)
	{
		if (!visited[node])
		{
			stack.push(node);
			visited[node] = true;
			do
			{
				neighbor = stack.top();
				stack.pop();
				for (iterator = g[neighbor].begin(), stop = g[neighbor].end() ; iterator != stop ; ++iterator)
					if (!visited[*iterator])
					{
						stack.push(*iterator);
						visited[*iterator] = true;
					}
			}
			while (!stack.empty());
			++components;
		}
	}
	return components;
}

int main (void)
{
	unsigned int n,m;
	std::ifstream input("dfs.in");
	input >> n >> m;
	unsigned int node1, node2;
	graph g(n + 1);
	while (m)
	{
		input >> node1 >> node2;
		g[node1].push_front(node2);
		g[node2].push_front(node1);
		--m;
	}
	input.close();
	unsigned int components(DepthFirstSearch(g));
	std::ofstream output("dfs.out");
	output << components << '\n';
	output.close();
	return 0;
}