Cod sursa(job #3167917)

Utilizator BledeaAlexBledea Alexandru BledeaAlex Data 11 noiembrie 2023 11:47:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

const int N_MAX = 100001;

vector<int> vecini[N_MAX];

int n, m, nrConexe;
bool viz[N_MAX];

void read(){
    f >> n >> m;
    for(int i = 0, n1, n2; i < m; ++i){
        f >> n1 >> n2;
        vecini[n1].push_back(n2);
        vecini[n2].push_back(n1); /// fiind neorientat, muchiile merg in doua sensuri
    }
}

void DFS(int nod){ /// = Depth first search
    viz[nod] = true;

    for(auto i : vecini[nod]){
        if( !viz[i])
            DFS(i);
    }
}

int main()
{
    read();

    for(int i = 1; i <= n; ++i){
        if( !viz[i]){
            nrConexe++;
            DFS(i);
        }
    }

    g << nrConexe;

    return 0;
}