Cod sursa(job #2930211)

Utilizator Alex18maiAlex Enache Alex18mai Data 27 octombrie 2022 18:51:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
//ALEX ENACHE

#include <fstream>
#include <vector>

using namespace std;

//ifstream cin("input"); ofstream cout("output");
ifstream cin("dfs.in"); ofstream cout("dfs.out");

/*
 Abordarea problemei de componente conexe utilizand DFS
*/

vector<vector<int>> gr; //lista de adiacenta
vector<bool> folosit; //marcam daca am trecut deja

void dfs(int nod){
    folosit[nod] = true;
    for (auto &vecin : gr[nod]){
        if (!folosit[vecin]){
            dfs(vecin);
        }
    }
}

int main() {

    int n, m;
    cin>>n>>m;

    gr.resize(n+1);
    folosit.resize(n+1, false);

    int a, b;
    for (int i=1; i<=m; i++){
        cin>>a>>b;

        //am muchie neorientata de la a la b -> adaug in lista vecinilor lui a pe b si in lista vecinilor lui b pe a
        gr[a].push_back(b);
        gr[b].push_back(a);
    }

    int compConexe = 0;
    for (int i=1; i<=n; i++){
        if (!folosit[i]){
            dfs(i);
            compConexe++;
        }
    }

    cout<<compConexe<<'\n';

    return 0;
}