Mai intai trebuie sa te autentifici.
Cod sursa(job #3196625)
Utilizator | Data | 24 ianuarie 2024 13:29:57 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.22 kb |
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <stack>
std::vector<std::vector<int> > listaAdiacenta;
std::vector<bool> vizitat;
// algoritm dfs
void DFS(int s){
std::stack<int> stiva;
stiva.push(s); // inseram nodul sursa in coada vida
vizitat[s] = true; // marcam nodul sursa ca vizitat
while(!stiva.empty()){
int nodSursa = stiva.top();
stiva.pop();
for(int &nodDest : listaAdiacenta[nodSursa]){
if(!vizitat[nodDest]){
stiva.push(nodDest);
vizitat[nodDest] = true; // marcam nodul muchiei ca vizitat
}
}
}
}
int main(){
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
int N, M;
fin >> N >> M;
vizitat.resize(N, false);
listaAdiacenta.resize(N);
for(int i = 0; i < M; i++){
int x, y;
fin >> x >> y;
x--;
y--;
listaAdiacenta[x].push_back(y);
listaAdiacenta[y].push_back(x);
}
fin.close();
int nrConex = 0;
for(int i = 0; i < N; i++){
if(!vizitat[i]){
DFS(i);
nrConex++;
}
}
fout << nrConex << "\n";
fout.close();
return 0;
}