Cod sursa(job #2383905)

Utilizator Marius92roMarius Marius92ro Data 19 martie 2019 21:16:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <stdbool.h>
#include <stdlib.h>
#include <fstream>
#include <vector>

using namespace std;

vector <int> *lista;

int nrNoduri = 0, nrMuchii = 0;
bool *vizitat;


void dfs(int nodStart){

    vizitat[nodStart] = true;

    int nrVecini = lista[nodStart].size();

    for ( int vecin = 0; vecin < nrVecini; vecin++)
                if ( !vizitat[lista[nodStart][vecin]] )
                       dfs(lista[nodStart][vecin]);

}

int main(){

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

    fin >> nrNoduri >> nrMuchii;

    lista = new vector<int>[nrNoduri + 5];

    if ( !lista ){
        cout <<"\n Nu a reusit alocarea dinamica !\n";
        exit(-1);
    }

    for (int i = 1; i <= nrMuchii; i++){

            int a, b;

            fin >> a >> b;

            lista[a].push_back(b);
            lista[b].push_back(a);
    }

    vizitat = new bool[nrNoduri + 5];

    for ( int i = 1; i <= nrNoduri; i++)
                            vizitat[i] = false;


    int nrComponente = 0;

    for ( int i = 1; i <= nrNoduri; i++)
            if ( !vizitat[i] ){
                    dfs(i);
                    nrComponente++;
            }

    fout << nrComponente;

    delete[] lista;
    delete[] vizitat;

    return 0;

}