Cod sursa(job #2924709)

Utilizator ralucarRogoza Raluca ralucar Data 9 octombrie 2022 10:36:18
Problema Parcurgere DFS - componente conexe Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n,m;
vector <vector<int>> lista_ad(100001);

void citire(){
    fin>>n>>m;
    int s,f;
    for(int i=0; i<m; i++){
        fin>>s>>f;
        lista_ad[s].push_back(f);
        lista_ad[f].push_back(s);
    }
}

void df(const int &nod, vector <int> &sel){
    sel[nod]=1;
    for(auto vec: lista_ad[nod]){
        if(sel[vec]==0)
            df(vec, sel);
    }
}

int nr_comp_conexe(){
    int nr=0;
    vector <int> sel(n,0);
    for(int i=1; i<=n;i++)
        if(sel[i]==0){
            nr++;
            df(i,sel);
        }
    return nr;
}


int main()
{
    citire();
    fout<<nr_comp_conexe();
    return 0;
}