Cod sursa(job #2797897)

Utilizator World_shifterMurgu Bogdan World_shifter Data 10 noiembrie 2021 18:44:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <vector>

using namespace std;

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

vector<vector<int> > edges;
vector<bool> viz;

void citire(){
    int n,m,a,b;
    in>>n>>m;
    edges.resize(n);
    viz.resize(n);
    for(int i=0; i<m; i++){
        in>>a>>b;
        a--;b--;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
}

void afis(){
    for(int i=0; i<edges.size(); i++){
        for(int j=0; j<edges[i].size(); j++){
            out<<edges[i][j]+1<<" ";
        }
        out<<"\n";
    }
}

void dfs(int node){
    viz[node]=true;
    int next;
    for(int i=0; i<edges[node].size(); i++){
        next=edges[node][i];
        if(!viz[next]){
            dfs(next);
        }
    }
}

int main()
{
    int comp_conex=0;
    citire();
    for(int i=0; i<edges.size(); i++){
        if(!viz[i]){
            comp_conex++;
            dfs(i);
        }
    }
    out<<comp_conex;
    return 0;
}