Pagini recente » Cod sursa (job #879102) | Cod sursa (job #1860377) | Cod sursa (job #2232464) | Cod sursa (job #2934021) | Cod sursa (job #193134)
Cod sursa(job #193134)
#include <vector>
#include <queue>
#include <cstdio>
#include <bitset>
int main (void)
{
std::vector<std::vector<unsigned int> > graf;
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w+", stdout);
unsigned int nrNoduri, nrMuchii, componente=0;
scanf("%u %u\n", &nrNoduri, &nrMuchii);
graf.resize(nrNoduri);
for (unsigned int muchie=0; muchie<nrMuchii; ++muchie) {
unsigned int src, dest;
scanf("%u %u\n", &src, &dest);
--src; --dest;
graf[src].push_back(dest);
graf[dest].push_back(src);
}
std::queue<unsigned int> Q;
std::bitset<100000> used;
unsigned int nod=0;
do {
Q.push(nod);
used.set(nod);
while (!Q.empty()) {
unsigned int crt = Q.front();
Q.pop();
for (std::vector<unsigned int>::const_iterator iter = graf[crt].begin();
iter != graf[crt].end(); ++iter)
if (!used.test(*iter)) { Q.push(*iter); used.set(*iter); }
}
for (nod=1; nod<nrNoduri && used.test(nod); ++nod);
++componente;
} while (nod < nrNoduri);
printf("%u\n", componente);
fclose(stdin);
fclose(stdout);
return 0;
}