Pagini recente » Cod sursa (job #1829914) | Cod sursa (job #1283244) | Cod sursa (job #1131603) | Cod sursa (job #1487140) | Cod sursa (job #3337944)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
fstream cin, cout;
queue<int> Q;
vector<vector<int>> M;
int n, m, Vizitat[100001];
int NrCompConexe, Nod1, Nod2;
void DFS(int NodCrt){
Vizitat[NodCrt] = 1;
for(int i = 0; i < M[NodCrt].size(); i++){
int Vecin = M[NodCrt][i];
if(!Vizitat[Vecin])
DFS(Vecin);
}
}
void BFS(){
while(!Q.empty()){
int NodCrt = Q.front();
for(int i = 0; i < M[NodCrt].size(); i++){
int Vecin = M[NodCrt][i];
if(!Vizitat[Vecin]){
Q.push(Vecin);
Vizitat[Vecin] = 1;
}
}
Q.pop();
}
}
int main()
{
cin.open("dfs.in", ios::in);
cout.open("dfs.out", ios::out);
cin >> n >> m;
M.resize(n + 1);
for(int i = 1; i <= m; i++){
cin >> Nod1 >> Nod2;
M[Nod1].push_back(Nod2);
M[Nod2].push_back(Nod1);
}
for(int i = 1; i <= n; i++){
if(!Vizitat[i]){
Q.push(i);
Vizitat[i] = 1;
BFS();
NrCompConexe++;
}
}
cout << NrCompConexe;
cin.close();
cout.close();
return 0;
}