Cod sursa(job #2323722)

Utilizator Robert_Marinescu_FMI_UVTMarinescu Robert Eugen Robert_Marinescu_FMI_UVT Data 19 ianuarie 2019 16:29:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int vizitat[100009];
int componente = 0;
vector <int> graf[100009];

void dfs(int nod){
    vizitat[nod] = 1;
    for(int i = 0; i<graf[nod].size();i++){
        if(vizitat[graf[nod][i]] == 0)
            dfs(graf[nod][i]);
    }

}

int main()
{   //Citire si declaratii
    int noduri, muchii, x, y;
    ifstream fin;
    fin.open("dfs.in");
    fin>>noduri>>muchii;
    for(int i=1;i<=muchii;i++){
        fin>>x>>y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    fin.close();

    //Apel dfs
    for(int i=1;i<=noduri;i++){
        if(vizitat[i] == 0){
            componente+=1;
            dfs(i);
        }
    }
    ofstream fout;
    fout.open("dfs.out");
    fout<<componente;
}