Pagini recente » Cod sursa (job #2684116) | Cod sursa (job #1055711) | Cod sursa (job #1536217) | Cod sursa (job #1832165) | Cod sursa (job #2789295)
#include <bits/stdc++.h>
using namespace std;
void DFS(int nod, vector<vector<int>> listaVecini, vector<int> &vizitat){
vizitat[nod] = 1; // vizitez nodul curent
// pentru fiecare vecin al nodului curent
for (auto i : listaVecini[nod]){
if (vizitat[i - 1] == 0){ // daca nu e vizitat atunci facem dfs pe el (avem i-1 pentru ca indicii pornesc de la 0 dar nodul meu e numerotat de la 1)
DFS(i - 1, listaVecini, vizitat);
}
}
}
int main(){
ifstream f("dfs.in");
ofstream g("dfs.out");
int n, // nr noduri
m, // nr muchii
muchie1, // primul nod al muchiei
muchie2, // al doilea nod al muchiei
nrComponenteConexe = 0;
vector<vector<int>> listaVecini; // lista de vecini al grafului
vector<int> vizitat; // vector care retine daca un nod a fost vizitat sau nu
f >> n >> m;
// pun in lista de vecini un vector care are pe prima pozitie nodul respectiv
for (int i = 1; i <= n; i++){
vector <int> aux;
aux.push_back(i);
listaVecini.push_back(aux);
}
// construiesc vectorul vizitat si pun pe fiecare pozitie 0 (niciun nod nu a fost vizitat inca)
for (int i = 0; i < n; i++){
vizitat.push_back(0);
}
// construire lista de vecini
for (int i = 0; i < m; i++){
f >> muchie1;
f >> muchie2;
listaVecini[muchie1 - 1].push_back(muchie2);
listaVecini[muchie2 - 1].push_back(muchie1);
}
// numarul de nrComponenteConexe = cand gasesc un nod care nu a fost inca vizitat dupa ce am facut dfs pe nodurile anterioare
for(int i = 0; i < n; i++){
if (vizitat[i] == 0){
nrComponenteConexe ++;
DFS(i, listaVecini, vizitat);
}
}
g << nrComponenteConexe;
return 0;
}