Cod sursa(job #191834)

Utilizator stefysStefan stefys Data 28 mai 2008 20:31:21
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#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;
}