Cod sursa(job #3318689)

Utilizator bianca_maneaManea Bianca bianca_manea Data 28 octombrie 2025 14:23:48
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
// Source: https://usaco.guide/general/io

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

vector<int> L[100001];
vector<int> viz(100001, 0);


void DFS(auto curr_node){
    viz[curr_node] = 1;
    for(auto i: L[curr_node]){
        if(viz[i] == 0){
            DFS(i);
        }
    }
}

int main(){
    int nr_muchii, nr_noduri, nod_x, nod_y, comp_conexe = 0;
    fin >> nr_noduri;
    fin >> nr_muchii;

    for (int i = 1; i<=nr_muchii; i++) {
        cin >> nod_x >> nod_y;

        L[nod_x].push_back(nod_y);
        L[nod_y].push_back(nod_x);
    }

    for(auto i = 1; i<=nr_noduri;i++){
        if(viz[i] == 0){
            comp_conexe++;
            DFS(i);
        }
    }

    fout << comp_conexe;

}