Pagini recente » Cod sursa (job #1621083) | Cod sursa (job #1160978) | Cod sursa (job #3146498) | Cod sursa (job #2836154) | Cod sursa (job #3196625)
#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;
}