Pagini recente » Cod sursa (job #3251981) | Cod sursa (job #1589340) | Cod sursa (job #1998789) | Cod sursa (job #970633) | Cod sursa (job #191834)
Cod sursa(job #191834)
#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;
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;
}