Cod sursa(job #2182558)

Utilizator AlexnolifeAlexandru Ica Alexnolife Data 22 martie 2018 14:42:34
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 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);
    }
}

//#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)
{
    for(const auto& neighbour : graph[source]) {
        if(!visited[neighbour]) {
            Traverse(neighbour);
            visited[neighbour] = true;
        }
    }
}

#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;
}