Cod sursa(job #3211880)

Utilizator BogdancxTrifan Bogdan Bogdancx Data 10 martie 2024 16:47:04
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <vector>

void DFS(const int nod, std::vector<bool>&visited, const std::vector<std::vector<int>>graf) {
    visited[nod] = true;

    for(const auto &i: graf[nod]) {
        if(visited[i] == false) {
            DFS(i, visited, graf);
        }
    }
}

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

    int noduri, muchii;
    fin>>noduri>>muchii;

    std::vector<std::vector<int>>graf(noduri+1);

    for(int i = 0; i < muchii; i++) {
        int a, b;
        fin>>a>>b;

        graf[a].push_back(b);
        graf[b].push_back(a);
    }

    std::vector<bool>visited(noduri+1, 0);
    int contor = 0;
    for(int i = 1; i <= noduri; i++) {
        if(visited[i] == 0) {
            ++contor;
            DFS(i, visited, graf);
        }
    }

    fout<<contor;

    fout.close();
    fin.close();
    return 0;
}