Cod sursa(job #3249404)

Utilizator Delian_04Dan Delian Delian_04 Data 16 octombrie 2024 10:22:33
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

vector<vector<int>> generare_lista_adiacenta(int varfuri, int muchii){
    vector<vector<int>> lista(varfuri);
    int x,y;
    for(int i=0; i<muchii; i++){
        fin>>x>>y;
        lista[x-1].push_back(y);
        lista[y-1].push_back(x);
    }
    return lista;
}

void DFS(vector<vector<int>> lista_adiacenta, int nod, vector<int>& componente, int cc){
    componente[nod]=cc;
    for(auto vecin: lista_adiacenta[nod]){
        if(!componente[vecin-1])
             DFS(lista_adiacenta, vecin-1, componente, cc);
    }
}

int main()
{
    int n,m;
    fin>>n>>m;
    vector<vector<int>> lista_adiacenta = generare_lista_adiacenta(n,m);

    vector<int> componente(n,0);
    int cc=0;
    for(int i=0; i<n; i++){
        if(componente[i]==0){
            cc++;
            DFS(lista_adiacenta, i, componente, cc);
        }
    }

    // for(int i=0; i<n; i++)
    //     fout<<componente[i]<<" ";
    fout<<cc;

    return 0;
}