Cod sursa(job #2907968)

Utilizator lolotbogdanLolot Stefan-Bogdan lolotbogdan Data 31 mai 2022 23:30:30
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int n, m; // nr de noduri, respectiv de muchii
vector<vector<int>>vecini; // liste de adiacenta
vector<bool>vizitat; // marcarea varfurilor vizitate
int nrComponenteConexe;

void dfs(int nod){

    vizitat[nod] = 1;

    for(int i = 0; i < vecini[nod].size(); i++){

        if(!vizitat[vecini[nod][i]]){
            vizitat[vecini[nod][i]] = 1;
            dfs(vizitat[vecini[nod][i]]);
        }
    }
}

int main(){

    f >> n >> m;

    vecini.resize(n + 1);
    vizitat.resize(n + 1, 0);

    for(int i = 0; i < m; i++){

        int u, v;

        f >> u >> v;

        vecini[u].push_back(v);
        vecini[v].push_back(u);
    }

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

    g << nrComponenteConexe;

    return 0;
}