Cod sursa(job #1803946)

Utilizator AkrielAkriel Akriel Data 12 noiembrie 2016 01:08:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#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();
}