Cod sursa(job #2890411)

Utilizator preda.andreiPreda Andrei preda.andrei Data 15 aprilie 2022 15:13:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

using Graph = vector<vector<int>>;

void VisitComponent(const Graph& graph, int node, vector<bool>& used) {
    queue<int> q;
    q.push(node);
    used[node] = true;

    while (!q.empty()) {
        node = q.front();
        q.pop();

        for (const auto& other : graph[node]) {
            if (!used[other]) {
                used[other] = true;
                q.push(other);
            }
        }
    }
}

int Solve(const Graph& graph) {
    vector<bool> used(graph.size(), false);
    auto res = 0;

    for (size_t i = 0; i < graph.size(); i += 1) {
        if (!used[i]) {
            res += 1;
            VisitComponent(graph, i, used);
        }
    }
    return res;
}

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

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

    Graph graph(nodes);
    for (int 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 = Solve(graph);
    fout << res << "\n";

    return 0;
}