Pagini recente » Cod sursa (job #3251569) | Cod sursa (job #3204492) | Cod sursa (job #1960948) | Cod sursa (job #398897) | Cod sursa (job #191835)
Cod sursa(job #191835)
#include <vector>
#include <cstdio>
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);
}
unsigned int *Q, *Q_push, *Q_pop;
std::vector<char> used; used.resize(nrNoduri);
unsigned int nod=0;
do {
Q_push = Q_pop = Q;
*(Q_push++) = nod;
while (Q_push - Q_pop > 0) {
unsigned int crt = *(Q_pop++);
used[crt]=1;
for (std::vector<unsigned int>::const_iterator iter = graf[crt].begin();
iter != graf[crt].end(); ++iter)
if (!used[*iter]) *(Q_push++) = *iter;
}
for (nod=1; nod<nrNoduri && used[nod]; ++nod);
++componente;
} while (nod < nrNoduri);
printf("%u\n", componente);
fclose(stdin);
fclose(stdout);
return 0;
}