Cod sursa(job #2928596)

Utilizator GeorgeNistorNistor Gheorghe GeorgeNistor Data 23 octombrie 2022 14:32:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <queue>

using namespace std;

vector<set<int>> graf;
vector<int> vc;

int N, M;
void citireGraf(){
    ifstream fin;
    fin.open("dfs.in");
    fin >> N >> M;
    graf = vector<set<int>>(N+1);
    vc = vector<int>(N+1);
    int nod_1, nod_2;
    for(int i = 1; i <= M; i++){
        fin >> nod_1 >> nod_2;
        graf[nod_1].insert(nod_2);
        graf[nod_2].insert(nod_1);
    }
    fin.close();
}
void DFS(int nod_start){
    //cout << nod_start << ' ';
    for(int nod_vecin: graf[nod_start]){
        if(!vc[nod_vecin]) {
            vc[nod_vecin] = 1;
            DFS(nod_vecin);
        }
    }
}
int Componente_Graf(){
    int c = 0;
    for(int i = 1; i <= N; i++){
        if(!vc[i]){
            c++;
            DFS(i);
        }
    }
    return c;
}

int main() {
    ofstream fout("dfs.out");
    citireGraf();
    fout << Componente_Graf();
    fout.close();
    return 0;
}