Pagini recente » Cod sursa (job #48267) | Cod sursa (job #3277975) | Cod sursa (job #2509357) | Cod sursa (job #675455) | Cod sursa (job #779228)
Cod sursa(job #779228)
#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;
}