Cod sursa(job #971966)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 10 iulie 2013 17:30:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <stack>
#include <list>

int main(void)
{
	std::ofstream out("dfs.out");
	std::ifstream in("dfs.in");
	int nV, nM, a, b, k;
	in >> nV >> nM;
	std::list<int> *arr = new std::list<int>[nV];
	bool *check = new bool[nV];
	for(int i = 0; i < nV; i++)
		check[i] = false;
	for(int i(0); i < nM; i++)
	{
		in >> a >> b; 
		a--;
		b--; 
		arr[a].push_back(b);
		arr[b].push_back(a);
	}
	for(int i(0); i < nV; i++)
	{
		if(check[i]) continue;
		k++;
		std::stack<int> myS;
		myS.push(i);
		check[i] = true;
		while(!myS.empty())
		{
			int n = myS.top();
			if(!arr[n].empty())
			{
				int m = arr[n].front();
				arr[n].pop_front();
				check[m] = true;
				myS.push(m);
				continue;
			}
			myS.pop();	
		}

	}
	out << k;
	return 0;
}