Cod sursa(job #2223874)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 21 iulie 2018 21:35:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>
#include <string>

using namespace std;

typedef vector<vector<int>> Graph;

const string IN_FILE = "dfs.in";
const string OUT_FILE = "dfs.out";

void dfs(const Graph& graph, const int u, vector<bool>& visited) {
    visited[u] = true;
    for (const auto& v : graph[u]) {
        if (!visited[v]) {
            dfs(graph, v, visited);
        }
    }
}

int countComponents(const Graph& graph) {
    int count = 0;
    auto visited = vector<bool>(int(graph.size()));
    for (int u = 0; u < int(graph.size()); u++) {
        if (!visited[u]) {
            count++;
            dfs(graph, u, visited);
        }
    }
    return count;
}

inline void addEdge(Graph& graph, const int u, const int v) {
    graph[u].push_back(v);
    graph[v].push_back(u);
}

Graph readGraph() {
    ifstream in(IN_FILE);
    int V, E;
    in >> V >> E;
    auto graph = Graph(V);
    for (int i = 0; i < E; i++) {
        int u, v;
        in >> u >> v;
        addEdge(graph, u - 1, v - 1);
    }
    return graph;
}

void writeOutput(const int components) {
    ofstream out(OUT_FILE);
    out << components << "\n";
    out.close();
}

int main() {
    const Graph& graph = readGraph();
    const int components = countComponents(graph);
    writeOutput(components);
    return 0;
}