Cod sursa(job #2244298)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 22 septembrie 2018 15:39:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
#include <assert.h>
#include <queue>
#include <chrono>
#include <memory>

using LL = long long;
using ULL = int long long;

const std::string _problemName = "dfs";

namespace std {
std::ifstream fin(_problemName + ".in");
std::ofstream fout(_problemName + ".out");
}

 #define USE_FILES

#ifdef USE_FILES
#define cin fin
#define cout fout
#endif

using graph_t = std::vector< std::vector<int> >;

class DFS {

public:

    DFS(std::unique_ptr<graph_t> graph) {
        graph_ = std::move(graph);

        visited_.resize(graph_->size());
        std::fill(visited_.begin(), visited_.end(), false);
    }

    std::unique_ptr<graph_t> releaseGraph() {
        return std::move(graph_);
    }

    void dfs(int node) {
        visited_[node] = true;

        for (auto neighbour : (*graph_)[node]) {
            if (!visited_[neighbour]) {
                dfs(neighbour);
            }
        }
    }

    bool visited(int node) {
        return visited_[node];
    }

private:

    std::unique_ptr<graph_t> graph_;
    std::vector<bool> visited_;

};

int main() {
    int n, m;
    std::cin >> n >> m;

    std::unique_ptr<graph_t> graph(new graph_t(n));

    while (m--) {
        int a, b;
        std::cin >> a >> b;
        --a, --b;

        (*graph)[a].push_back(b);
        (*graph)[b].push_back(a);
    }

    DFS dfs(std::move(graph));

    int compCount = 0;

    for (int node = 0; node < n; ++node) {
        if (!dfs.visited(node)) {
            dfs.dfs(node);
            ++compCount;
        }
    }

    std::cout << compCount << '\n';

    return 0;
}