Cod sursa(job #3122191)

Utilizator preda.andreiPreda Andrei preda.andrei Data 17 aprilie 2023 20:02:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <vector>

using namespace std;

using Graph = vector<vector<int>>;

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

int CountComps(const Graph& graph) {
    auto visited = vector<bool>(graph.size(), false);
    auto comps = 0;

    for (size_t i = 0; i < graph.size(); i += 1) {
        if (!visited[i]) {
            comps += 1;
            VisitComp(graph, visited, i);
        }
    }
    return comps;
}

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

    int nodes, edges;
    fin >> nodes >> edges;

    auto graph = Graph(nodes);
    for (auto i = 0; i < edges; i += 1) {
        int a, b;
        fin >> a >> b;
        graph[a - 1].push_back(b - 1);
        graph[b - 1].push_back(a - 1);
    }

    auto res = CountComps(graph);
    fout << res << "\n";

    return 0;
}