Pagini recente » Cod sursa (job #2756574) | Cod sursa (job #1191282) | Cod sursa (job #477329) | Sedinta 2007-11-07 | Cod sursa (job #1803946)
#include <iostream>
#include <fstream>
#define N 100005
using namespace std;
ifstream f ("dfs.in");
ofstream g ("dfs.out");
struct node
{
int info;
node *next;
};
node *root[N], *top[N];
int totalNodes, totalEdges;
bool visited[N];
void nodePush(int index, int value)
{
node *aux = new node;
aux -> info = value;
if ( root[index] )
{
top[index] -> next = aux;
top[index] = top[index] -> next;
}
else
root[index] = top[index] = aux;
top[index] -> next = NULL;
}
inline void readVariables()
{
f >> totalNodes >> totalEdges;
int x, y;
for ( ; totalEdges ; totalEdges-- )
{
f >> x >> y;
nodePush(x, y);
nodePush(y, x);
}
}
void depthFirstTraversal(int currentNode)
{
visited[currentNode] = true;
for ( node *it = root[currentNode]; it ; it = it -> next )
{
if ( visited[it->info] == false )
depthFirstTraversal(it->info);
}
}
int calculateSolution()
{
int counter = 0;
for ( int indexNode = 1; indexNode <= totalNodes; indexNode++ )
if ( visited[indexNode] == false )
{
counter++;
depthFirstTraversal(indexNode);
}
return counter;
}
int main()
{
readVariables();
g << calculateSolution();
}