Cod sursa(job #191833)

Utilizator stefysStefan stefys Data 28 mai 2008 20:28:36
Problema Parcurgere DFS - componente conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#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);
		while (!Q.empty()) {
			unsigned int crt = Q.front();
			Q.pop();
			used.set(crt);
			for (std::vector<unsigned int>::const_iterator iter = graf[crt].begin();
					iter != graf[crt].end(); ++iter)
				if (!used.test(*iter)) Q.push(*iter);
		}
		for (nod=1; nod<nrNoduri && used.test(nod); ++nod);
		++componente;
	} while (nod < nrNoduri);
	
	printf("%u\n", componente);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}