Cod sursa(job #3352277)

Utilizator gugalcromMuntoiu Vlad-Ioan gugalcrom Data 26 aprilie 2026 11:45:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

struct GrafNeorientat {
    vector<vector<int>> v;
    GrafNeorientat(int N) : v(N), vizitat(N) {}
    void trasare(int a, int b) {
        v[a].push_back(b);
        v[b].push_back(a);
    }
    vector<int> vizitat;
    int componente_conexe() {
        int cate = 0;
        for(int i=0; i<vizitat.size(); ++i) {
            if(!vizitat[i]) {
                dfs(i);
                ++cate;
            }
        }
        return cate;
    }
    void dfs(int nod) {
        vizitat[nod] = 1;
        for(auto vecin: v[nod]) {
            if(!vizitat[vecin]) {
                dfs(vecin);
            }
        }
    }
};

int main() {
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    int N, M;
    fin >> N >> M;
    GrafNeorientat G(N);
    for(int i=0; i<M; ++i) {
        int a, b;
        fin >> a >> b;
        G.trasare(a-1, b-1);
    }
    fout << G.componente_conexe() << '\n';
    return 0;
}