Cod sursa(job #2971355)

Utilizator CalinachoGherlan Calin Paul Calinacho Data 27 ianuarie 2023 09:07:25
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include<bits/stdc++.h>
using namespace std;

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

struct node{
    bool val=1;
    int nrv=0;
    vector<int>vecini={};
};

void dfs(node G[], int now){
    G[now].val=0;
    for(int i=0;i<G[now].nrv;i++){
        if(G[G[now].vecini[i]].val){
            dfs(G, G[now].vecini[i]);
        }
    }
    return;
}

void updVal(node G[], int x, int y){
    G[x].val=y;
    return;
}

void addEdge(node G[], int x, int y){
    G[x].vecini.push_back(y);
    G[y].vecini.push_back(x);
    G[x].nrv++;
    G[y].nrv++;
    return;
}

void printGraph(node G[], int n){
    for(int i=0;i<n;i++){
        cout<<"Node "<<i<<" has value: "<<G[i].val<<". Neighbors: ";
        for(int j=0;j<G[i].nrv;j++){
            cout<<G[i].vecini[j]<<" ";
        }
        cout<<"\n";
    }
}

    int main(){
        int n, m, a, b, rasp=0;
        in>>n>>m;
        node G[n];
        for(int i=0;i<m;i++){
            in>>a>>b;
            addEdge(G, a, b);
        }
        
        for(int i=0;i<n;i++){
            if(G[i].val){
                rasp++;
                dfs(G, i);
            }
        }
        
        out<<rasp;
        
}