Cod sursa(job #2244287)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 22 septembrie 2018 15:31:29
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 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);
    }
    
    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_;

};

void dfs(int node) {

}

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

    std::unique_ptr<graph_t> graph = std::make_unique<graph_t>(n);

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

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

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