Cod sursa(job #3337944)

Utilizator Denis20008924Mitrasca Denis Denis20008924 Data 30 ianuarie 2026 21:08:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

fstream cin, cout;

queue<int> Q;
vector<vector<int>> M;
int n, m, Vizitat[100001];
int NrCompConexe, Nod1, Nod2;

void DFS(int NodCrt){
    Vizitat[NodCrt] = 1;
    for(int i = 0; i < M[NodCrt].size(); i++){
        int Vecin = M[NodCrt][i];
        if(!Vizitat[Vecin])
            DFS(Vecin);
    }
}

void BFS(){
    while(!Q.empty()){
        int NodCrt = Q.front();
        for(int i = 0; i < M[NodCrt].size(); i++){
            int Vecin = M[NodCrt][i];
            if(!Vizitat[Vecin]){
                Q.push(Vecin);
                Vizitat[Vecin] = 1;
            }
        }
        Q.pop();
    }
}

int main()
{
    cin.open("dfs.in", ios::in);
    cout.open("dfs.out", ios::out);

    cin >> n >> m;
    M.resize(n + 1);
    for(int i = 1; i <= m; i++){
        cin >> Nod1 >> Nod2;
        M[Nod1].push_back(Nod2);
        M[Nod2].push_back(Nod1);
    }

    for(int i = 1; i <= n; i++){
        if(!Vizitat[i]){
            Q.push(i);
            Vizitat[i] = 1;
            BFS();
            NrCompConexe++;
        }
    }
    cout << NrCompConexe;

    cin.close();
    cout.close();

    return 0;
}