Cod sursa(job #3249420)

Utilizator Delian_04Dan Delian Delian_04 Data 16 octombrie 2024 10:55:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb

    ///Componente Conexe - varianta iterativa
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

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

void DFS_iter(vector<vector<int>>& lista, int nod_start, vector<int>& componente, int cc){
    stack<int> stiva;
    stiva.push(nod_start);
    componente[nod_start-1]=cc;
    while(!stiva.empty()){
        int nod=stiva.top();
        stiva.pop();

        for(auto vecin: lista[nod-1]){
            if(componente[vecin-1]==0){
                stiva.push(vecin);
                componente[vecin-1]=cc;
            }
        }
    }
}

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

    vector<int> componente(n,0);
    int cc=0;

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

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