Pagini recente » Cod sursa (job #2780384) | Cod sursa (job #507821) | Cod sursa (job #1989650) | Cod sursa (job #1445051) | Cod sursa (job #2930206)
//ALEX ENACHE
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
//ifstream cin("input"); ofstream cout("output");
ifstream cin("dfs.in"); ofstream cout("dfs.out");
/*
Abordarea problemei de componente conexe utilizand BFS
*/
vector<vector<int>> gr; //lista de adiacenta
vector<bool> folosit; //marcam daca am trecut deja
queue<int> q; //coada ca la lee cu indicele nodului
void bfs(int s){
folosit[s] = true;
q.push(s);
while(!q.empty()){
int nodCurent = q.front(); // ne scoatem nodul curent din coada
q.pop();
for (auto &vecin : gr[nodCurent]){ // mergem in toti vecinii nodului curent
if (!folosit[vecin]){
folosit[vecin] = true;
q.push(vecin); //adaugam vecinul in coada
}
}
}
}
int main() {
int n, m;
cin>>n>>m;
gr.resize(n+1);
folosit.resize(n+1, false);
int a, b;
for (int i=1; i<=m; i++){
cin>>a>>b;
//am muchie neorientata de la a la b -> adaug in lista vecinilor lui a pe b si in lista vecinilor lui b pe a
gr[a].push_back(b);
gr[b].push_back(a);
}
int compConexe = 0;
for (int i=1; i<=n; i++){
if (!folosit[i]){
bfs(i);
compConexe++;
}
}
cout<<compConexe<<'\n';
return 0;
}