Cod sursa(job #3253191)

Utilizator Ioana38Bejenaru Ioana Ioana38 Data 1 noiembrie 2024 21:13:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
using namespace std;
#include <vector>

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

std::vector <std::vector<int>> lista;
std::vector <bool> viz;

void Construieste(int N, int M)
{
    int x, y;
    for(int i = 0; i < M; i++)
    {
        fin >> x >> y;
        lista[x - 1].push_back(y - 1);
        lista[y - 1].push_back(x - 1);
    }
}

void DFS(int nod)
{
    viz[nod] = 1;
    int size = lista[nod].size();
    for(int i = 0; i < size; i++)
        if(!viz[lista[nod][i]])
            DFS(lista[nod][i]);
}

int main() {
    int N, M;
    fin >> N >> M;
    lista.resize(N);
    Construieste(N, M);
    viz.resize(N, 0);
    int componente_conexe = 0;
    for(int i = 0; i < N; i++)
        if(!viz[i])
        {
            DFS(i); componente_conexe ++;
        }
    fout << componente_conexe;
}