Cod sursa(job #948150)

Utilizator sebii_cSebastian Claici sebii_c Data 9 mai 2013 15:59:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <vector>

using namespace std;

template <class T>
class graph {
public:
    graph() {}

    template <class ForwardIterator>
    graph(ForwardIterator begin, ForwardIterator end)
        : nodes(begin, end) {}

    void add_edge(T src, T dst) {
        nodes.insert(src);
        nodes.insert(dst);
        edges[src].push_back(dst);
        edges[dst].push_back(src);
    }

    int connected_components() {
        int result = 0;

        unordered_set<T> visited;
        for (T node : nodes) {
            if (visited.count(node) == 0) {
                ++result;
                dfs(node, visited);
            }
        }

        return result;
    }

private:
    void dfs(T node, unordered_set<T>& visited) {
        visited.insert(node);

        for (T next : edges[node]) {
            if (visited.count(next) == 0)
                dfs(next, visited);
        }
    }

    unordered_set<T> nodes;
    unordered_map<T, vector<T>> edges;
};

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

    int N, M;
    fin >> N >> M;

    vector<int> v(N);
    for (int i = 1; i <= N; ++i)
        v[i - 1] = i;

    graph<int> g(begin(v), end(v));
    for (int i = 0; i < M; ++i) {
        int x, y;
        fin >> x >> y;
        g.add_edge(x, y);
    }

    fout << g.connected_components() << "\n";

    return 0;
}