Cod sursa(job #3368317)

Utilizator ilinca_onofreiIlinca-Ioana Onofrei ilinca_onofrei Data 14 octombrie 2026 11:03:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");
const int MAXN=100005;
vector<int> a[MAXN];
bool vizitat[MAXN];

void dfs(int nod) {
    vizitat[nod]=true; // nodul curent
    for (int vecin:a[nod]) {
        if (!vizitat[vecin])
            dfs(vecin); // daca vecinul nu a fost vizitat mergem pe el
    }
}

int main() {

    int n, m; // n noduri si m muchii
    fin>>n>>m;
    for (int i=0;i<m;i++) {
        int u,v;
        fin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    int componente=0;
    for (int i=1;i<=n;i++) {
        if (!vizitat[i]) { //nod nevizitat => o noua componenta conexa
            componente++;
            dfs(i);
        }
    }
    fout<<componente<<"\n";
}