Cod sursa(job #2182562)

Utilizator AlexnolifeAlexandru Ica Alexnolife Data 22 martie 2018 14:49:06
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <iostream>
#include <vector>
#include <array>
#include <utility>
#include <queue>
#include <fstream>
#include <limits>

std::ofstream g("dfs.out");

std::array<std::vector<int>, 100001> graph;
std::vector<bool> visited(100001, false);
// std::vector<bool> isInQueue(100001, false);
// std::queue<int> nextNodes;

int numNodes, numEdges, source;

void ReadGraph()
{
    std::ifstream f("dfs.in");

    f >> numNodes >> numEdges; // >> source;

    int node, neighbour;

    for(int i = 1; i <= numEdges; ++i) {
        f >> node >> neighbour;

        graph[node].emplace_back(neighbour);
        graph[neighbour].emplace_back(node);
    }
}

//#define BFS_TRAVERSAL
#define DFS_TRAVERSAL

#ifdef BFS_TRAVERSAL

void Traverse()
{
    nextNodes.emplace(source);
    isInQueue[source] = true;
    cost[source] = 0;

    while(!nextNodes.empty()) {
        const auto& currentNode = nextNodes.front();

        for(const auto& neighbour : graph[currentNode]) {
            if(cost[currentNode] + 1 < cost[neighbour]) {
                cost[neighbour] = cost[currentNode] + 1;
            }

            if(!visited[neighbour] && !isInQueue[neighbour]) {
                nextNodes.emplace(neighbour);
                isInQueue[neighbour] = true;
            }
        }

        visited[currentNode] = true;
        nextNodes.pop();
    }
}

#endif // BFS_TRAVERSAL

#ifdef DFS_TRAVERSAL

void Traverse(int source)
{
    visited[source] = true;

    for(const auto& neighbour : graph[source])
        if(!visited[neighbour])
            Traverse(neighbour);
}

#endif // DFS_TRAVERSAL

int main()
{
    ReadGraph();

    unsigned int cnt = 0;

    for(int i = 1; i <= numNodes; ++i) {
        if(!visited[i]) {
            Traverse(i);
            ++cnt;
        }
    }

    g << cnt;

    return 0;
}