Cod sursa(job #3224992)

Utilizator valeriualbValeriu Alb valeriualb Data 16 aprilie 2024 19:08:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <vector>

static size_t node_count;
static std::vector<std::vector<size_t>> adjacency;
static std::vector<bool> visited;

void dfs(size_t source) {
    visited[source] = true;

    for (size_t neighbor : adjacency[source]) {
        if (!visited[neighbor])
            dfs(neighbor);
    }
}

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

    size_t line_count;
    in >> node_count;
    in >> line_count;

    std::vector<size_t> empty_vector;
    adjacency.insert(adjacency.begin(), node_count + 1, empty_vector);
    visited.insert(visited.begin(), node_count + 1, false);

    for (size_t index = 1; index <= line_count; index++) {
        size_t source, destination;
        in >> source >> destination;
        adjacency[source].push_back(destination);
        adjacency[destination].push_back(source);
    }

    size_t components = 0;
    for (size_t source = 1; source <= node_count; source++) {
        if (!visited[source]) {
            dfs(source);
            components++;
        }
    }

    out << components << '\n';
    return 0;
}