Cod sursa(job #1800764)

Utilizator mariusadamMarius Adam mariusadam Data 8 noiembrie 2016 01:59:07
Problema Parcurgere DFS - componente conexe Scor 75
Compilator cpp Status done
Runda Arhiva educationala Marime 2.35 kb
//
// Created by marius on 11/8/16.
//

#include <fstream>
#include <vector>
#include <map>
#include <cstring>

using namespace std;

class Edge
{
private:
    int first;

private:
    int second;
public:

    Edge() {}

    Edge(int first, int second) : first(first), second(second) {}
    int getFirst() const {
        return first;
    }

    int getSecond() const {
        return second;
    }

    Edge& setFirst(int first) {
        this->first = first;

        return *this;
    }

    Edge& setSecond(int second) {
        this->second = second;

        return *this;
    }

    friend std::istream& operator>> (std::istream &in, Edge & edge)
    {
        in >> edge.first;
        in >> edge.second;

        return in;
    }
};

class Graph
{
private:
    int numberOfVertices;
    map<int, vector<int>> nodes;

    void dfs(int start, bool marked[])
    {
        marked[start] = true;

        if (this->nodes.find(start) == this->nodes.end()) {
            return;
        }

        for(auto node : this->nodes.find(start)->second) {
            if (!marked[node]) {
                this->dfs(node, marked);
            }
        }
    }
public:
    Graph(int numberOfVertices) : numberOfVertices(numberOfVertices) {}

    void addEdge(const Edge & edge) {
        if (this->nodes.find(edge.getFirst()) == this->nodes.end()) {
            this->nodes.insert(make_pair(edge.getFirst(), vector<int>()));
        }
        if (this->nodes.find(edge.getSecond()) == this->nodes.end()) {
            this->nodes.insert(make_pair(edge.getSecond(), vector<int>()));
        }

        this->nodes.find(edge.getFirst())->second.push_back(edge.getSecond());
        this->nodes.find(edge.getSecond())->second.push_back(edge.getFirst());
    }

    int getNrComponenteConexe() {
        bool marked[this->numberOfVertices];
        memset(marked, 0, sizeof(marked));

        int cnt = 0;
        for(int i = 1; i <= this->numberOfVertices; i++) {
            if (!marked[i]) {
                this->dfs(i, marked);
                cnt++;
            }
        }

        return cnt;
    }
};

int main() {
    ifstream in("dfs.in");
    ofstream out("dfs.out");

    int n, m;

    in >> n >> m;

    Graph graph(n);
    Edge edge;

    for(; m; m--) {
        in >> edge;
        graph.addEdge(edge);
    }

    out << graph.getNrComponenteConexe();

    in.close();
    out.close();

    return 0;
}