Cod sursa(job #2656811)

Utilizator UtilizatorGBGeorge Bodea UtilizatorGB Data 8 octombrie 2020 19:31:30
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

#define MAX_N 100000
#define MAX_M 200000
int vizite[MAX_N+1];
vector<int> listaVecini[MAX_M];

void parcurgereDFS(int nodStart) {
    vizite[nodStart] = 1;

    for (int i = 0; i < listaVecini[nodStart].size(); i++) {
        int vecin = listaVecini[nodStart][i];
        if (vizite[vecin] == 0)
            parcurgereDFS(vecin);
    }
}

int gasireNumarConexe(int nrNoduri) {
    int componenteConexe = 0;

    for (int i = 1; i <= nrNoduri; i++)
        if (vizite[i] == 0){
            parcurgereDFS(i);
            componenteConexe++;
        }

    return componenteConexe;
}


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

int main() {
    int n,m;
    f>>n>>m;
    for (int i = 0; i < m; i++) {
        int sursa, destinatie;
        f>>sursa>>destinatie;
        listaVecini[sursa].emplace_back(destinatie);
    }

    g<<gasireNumarConexe(n);

    f.close();
    g.close();
    return 0;
}