Cod sursa(job #3250937)

Utilizator Cristi1123Lucan Crisitian Cristi1123 Data 24 octombrie 2024 11:11:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <fstream>
using namespace std;

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

void dfs(int start, const vector<vector<int>>& addiacence, unordered_set<int>& visited){
    queue<int> to_visit;
    visited.insert(start);
    to_visit.push(start);

    while (!to_visit.empty()){
        int curr = to_visit.front();
        for (const auto& neighbour : addiacence[curr])
            if (visited.find(neighbour) == visited.end()){
                to_visit.push(neighbour);
                visited.insert(neighbour);
            }
        to_visit.pop();
    }

}

int main(){
    int nr_nodes, nr_links;
    fin >> nr_nodes >> nr_links;

    vector<vector<int>> addiacence(nr_nodes + 1);
    for (int i = 0; i < nr_links; ++i){
        int node1, node2;
        fin >> node1 >> node2;
        addiacence[node1].push_back(node2);
        addiacence[node2].push_back(node1);
    }

    unordered_set<int> visited;
    int nr_components = 0;
    for (int i = 1; i <= nr_nodes; ++i)
        if (visited.find(i) == visited.end()){
            nr_components ++;
            dfs(i, addiacence, visited);
        }
    fout << nr_components;
}