Cod sursa(job #3368431)

Utilizator yolanqaStefanescu Yolanda - Gabriela yolanqa Data 14 octombrie 2026 14:39:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <unordered_map>
#include <vector>
#include <fstream>

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

std::vector<bool> parcurs;
std::vector<std::vector<int>>graf;
//std::unordered_map<int,std::pair<int,int>> graf = {{1, {2,3} }, {2, {1,4}}, {3, {1,4}}};

//int forward(int position) {
    //return parcurs[position+1];}

void dfs(int node) {
    parcurs[node] = 1;
    for (int i : graf[node]) {
        if (parcurs[i]==0)
            dfs(i);
    }
}

//1-2-3
//3-4
//4-5
int main() {

    int n, m;
    if (!(fin >> n >> m))
        return 0;

    graf.resize(n + 1);
    parcurs.resize(n + 1, 0);

    for (int i = 0; i < m; ++i) {
        int x, y;
        fin >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }


    int componente_conexe = 0;
    for (int i = 1; i <= n; ++i) {

        if (!parcurs[i]) {
            componente_conexe++;
            dfs(i);
        }
    }

    fout << componente_conexe;
    return 0;
}