Cod sursa(job #3314514)

Utilizator dumy123Darius Dumitrascu dumy123 Data 10 octombrie 2025 11:43:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <vector>
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
void dfs(std::vector<bool> &viz,int i,std::vector <std::vector<int>> &lista){
    viz[i]=true;
    for(int j=0;j<lista[i].size();j++){
        if(viz[lista[i][j]]==false){
            dfs(viz,lista[i][j],lista);
        }
    }
}
int main(){
    int n,m,x,y,nr=0;
    fin>>n>>m;
    std::vector <bool>viz (n+1);
    std::vector <std::vector<int>> lista(n+1);
    while(m){
        fin>>x>>y;
        lista[x].push_back(y);
        lista[y].push_back(x);
        m--;
    }
    for(int i=1;i<=n;i++){
        if(viz[i]==false){
            nr++;
            dfs(viz,i,lista);
        }
    }
    fout<<nr;
    // for(int i=1;i<=n;i++){
    //     std::cout<<i<<": ";
    //     for(int j=0;j<lista[i].size();j++){
    //         std::cout<<lista[i][j]<<" ";
    //     }
    //     std::cout<<"\n";
    // }
    //fout<<nr;   
    return 0;
}