Pagini recente » Cod sursa (job #1493102) | Cod sursa (job #89796) | Cod sursa (job #3237329) | Cod sursa (job #1641028) | Cod sursa (job #2541922)
using namespace std;
#define fisier "dfs"
#ifdef fisier
#include <fstream>
ifstream in(fisier ".in");
ofstream out(fisier ".out");
#else
#include <iostream>
#define in cin
#define out cout
#endif
const int
MAX_N = 100000;
int coada[MAX_N], baza, varf, n;
bool explorat[MAX_N];
#include <vector>
vector<int> de_la[MAX_N];
void add_in_coada(int nod) {
if (!explorat[nod]) {
coada[varf++] = nod;
explorat[nod] = true;
}
}
void bfs(int nod_sursa) {
add_in_coada(nod_sursa);
for (; baza < varf; baza++) {
for (
vector<int>::iterator vecin = de_la[coada[baza]].begin();
vecin != de_la[coada[baza]].end();
vecin++
) {
//out << coada[baza] << " --> " << *vecin << endl;
add_in_coada(*vecin);
}
}
}
int componente_conexe() {
int cmp_cnx = 0;
for (int nod = 0; nod < n; nod++) {
if (!explorat[nod]) {
cmp_cnx++;
bfs(nod);
}
}
return cmp_cnx;
}
int main() {
int m, x, y;
in >> n >> m;
while (m--) {
in >> x >> y;
x--; y--;
de_la[x].push_back(y);
de_la[y].push_back(x);
}
out << componente_conexe();
}
//