Cod sursa(job #3292312)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 7 aprilie 2025 20:41:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <vector>

using namespace std;

int current_component = 0;

vector<int> comps;
vector<vector<int>> arcs;
    

void bfs(int node) {
    comps[node] = current_component;
    
    for(unsigned int i=0; i<arcs[node].size(); ++i) {
        int next_node = arcs[node][i];
        if (comps[next_node] == 0) {
            bfs(next_node);
        }
    }
}

int main() {
    int n, m;
    
    fstream infile;
    infile.open("dfs.in", fstream::in);

    fstream outfile;
    outfile.open("dfs.out", fstream::out);

    infile>>n>>m;

    comps.resize(n+1);
    arcs.resize(n+1);
    
    for(int i=0; i<=m; ++i) {
        int s, d;
        infile>>s>>d;
        arcs[s].push_back(d);    
        arcs[d].push_back(s);
    }
    
    for(int i=1; i<=n; ++i) {
        if (comps[i] == 0) {
            ++current_component;
            bfs(i);
        }
    }
    
    outfile<<current_component<<"\n";

    return 0;
}