Cod sursa(job #779228)

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

#include <cstdio>

struct linked_list
{
	unsigned int vertex;
	struct linked_list *next;
};

const unsigned int MAX_VERTICES(100001);

struct linked_list *graph [MAX_VERTICES];

unsigned int DepthFirstSearch (unsigned int n)
{
	bool *visited(new bool [n]( ));
	unsigned int *stack(new unsigned int [n]), *stack_ptr;
	struct linked_list *iterator;
	unsigned int components(0), neighbor;
	for (unsigned int node(1) ; node < n ; ++node)
		if (!visited[node])
		{
			stack_ptr = stack;
			*stack_ptr = node;
			visited[node] = true;
			do
			{
				neighbor = *stack_ptr;
				--stack_ptr;
				for (iterator = graph[neighbor] ; iterator ; iterator = iterator->next)
					if (!visited[iterator->vertex])
					{
						++stack_ptr;
						*stack_ptr = iterator->vertex;
						visited[iterator->vertex] = true;
					}
			}
			while (stack_ptr >= stack);
			++components;
		}
	delete [ ] visited;
	delete [ ] stack;
	return components;
}

int main (void)
{
	std::freopen("dfs.in","r",stdin);
	std::freopen("dfs.out","w",stdout);
	unsigned int n, m;
	std::scanf("%u%u",&n,&m);
	unsigned int node1, node2, *node1_ptr(&node1), *node2_ptr(&node2);
	struct linked_list *new_vertex;
	while (m)
	{
		std::scanf("%u%u",node1_ptr,node2_ptr);
		new_vertex = new struct linked_list;
		new_vertex->vertex = node2;
		new_vertex->next = graph[node1];
		graph[node1] = new_vertex;
		new_vertex = new struct linked_list;
		new_vertex->vertex = node1;
		new_vertex->next = graph[node2];
		graph[node2] = new_vertex;
		--m;
	}
	std::fclose(stdin);
	std::printf("%u\n",DepthFirstSearch(n + 1));
	std::fclose(stdout);
	return 0;
}