Cod sursa(job #3250630)

Utilizator Bogdan345Marius Mihalache Bogdan345 Data 22 octombrie 2024 15:51:01
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <vector>
using namespace std;
vector<int>tata;
vector<vector<int>>gr;
void DFS(int nod){
    for(int i=0;i<gr[nod].size();i++){
        if(tata[gr[nod][i]]==-1){
            tata[gr[nod][i]]=nod;
            DFS(gr[nod][i]);
        }//else if(tata[nod]!=gr[nod][i]){

        //}     
    }
}
int main(){
    int n,m,nod1,nod2,nr_comp=0;
    cin>>n>>m;
    tata.resize(n+1,-1);
    gr.resize(n+1);
    for(int i=1;i<=m;i++){
        cin>>nod1>>nod2;
        gr[nod1].push_back(nod2);
        gr[nod2].push_back(nod1);
    }
    for(int i=1;i<=n;i++){
        if(tata[i]==-1){
            DFS(i);
            nr_comp++;
        }
    }
    cout<<nr_comp<<'\n';
    tata.clear();
    gr.clear();
}