Cod sursa(job #3337943)

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

using namespace std;

fstream cin, cout;

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);
    }
}

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]){
            DFS(i);
            NrCompConexe++;
        }
    }
    cout << NrCompConexe;

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

    return 0;
}