Pagini recente » Cod sursa (job #2631527) | Cod sursa (job #1474286) | Borderou de evaluare (job #1080147) | Cod sursa (job #786383) | Cod sursa (job #2930211)
//ALEX ENACHE
#include <fstream>
#include <vector>
using namespace std;
//ifstream cin("input"); ofstream cout("output");
ifstream cin("dfs.in"); ofstream cout("dfs.out");
/*
Abordarea problemei de componente conexe utilizand DFS
*/
vector<vector<int>> gr; //lista de adiacenta
vector<bool> folosit; //marcam daca am trecut deja
void dfs(int nod){
folosit[nod] = true;
for (auto &vecin : gr[nod]){
if (!folosit[vecin]){
dfs(vecin);
}
}
}
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]){
dfs(i);
compConexe++;
}
}
cout<<compConexe<<'\n';
return 0;
}