Pagini recente » Cod sursa (job #1670679) | Cod sursa (job #2250312) | Cod sursa (job #1506982) | Cod sursa (job #2363227) | Cod sursa (job #2277561)
#include <fstream>
#include <vector>
using namespace std;
#define N_MAX 100005
ifstream cin{"dfs.in"};
ofstream cout{"dfs.out"};
int n, nr_comp;
vector<int> graf[N_MAX];
vector<int> d(N_MAX, -1);
int q[N_MAX];
void citeste() {
int m;
cin >> n >> m;
while (m--){
int i, j;
cin >> i >> j;
graf[i].push_back(j);
graf[j].push_back(i);
}
}
void BFS(int start) {
int stg = 0, drp = 0;
q[stg] = start;
d[start] = 0;
for (; stg <= drp; ++stg) {
int current = q[stg];
for (auto& nod : graf[current])
if (nod != start && d[nod] == -1) {
d[nod] = d[current] + 1;
q[++drp] = nod;
}
}
}
void rezolva() {
for (int i = 1; i <= n; ++i)
if (d[i] == -1) {
++nr_comp;
BFS(i);
}
}
int main()
{
citeste();
rezolva();
cout << nr_comp;
}