Cod sursa(job #2924499)

Utilizator tiberiusss26Titiriga Tiberiu Nicolae tiberiusss26 Data 3 octombrie 2022 19:25:19
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>

#include <vector>
using namespace std;
// graf - matrice adiacenta, lista adiacenta, lista de muchii

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

class graf {
    vector<vector<int>> lista_ad;
    int n, m;
public:
    graf(const vector<vector<int>> &listaAd, int n, int m) : n(n), m(m) {
        for(auto v: listaAd){
            lista_ad.push_back(v);
        }
    }

    void dfs(int nod, vector<int>sol ){
        sol[nod] = 1;
        for ( auto vec: lista_ad[nod]){
            if( sol[vec] == 0)
                dfs(vec, sol);
        }
    }

    int nrCompConexe() {
        int k = 0;
        vector<int> sol(n+1,0);
        for(int i = 1;i <= n; i++){
            if( sol[i] == 0){
                k++;
                dfs(i,sol);
            }
        }
        return k;
    }

    virtual ~graf() {

    }
};

int main() {
    int n,m,x,y;
    vector<vector<int>> lista_ad(100);
    f>>n>>m;
    for(int i =0; i<m;i++) {
        f >> x >> y;
        lista_ad[x].push_back(y);
    }
    graf gg = graf(lista_ad,n,m);
    g<<gg.nrCompConexe();
}