Cod sursa(job #3250631)

Utilizator Bogdan345Marius Mihalache Bogdan345 Data 22 octombrie 2024 15:54:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
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){
            tata[i]=i;
            DFS(i);
            nr_comp++;
        }
    }
    cout<<nr_comp<<'\n';
    tata.clear();
    gr.clear();
}