Cod sursa(job #971958)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 10 iulie 2013 16:55:02
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <stack>
#include <list>

struct Vertex
{
	std::list<int> myL;
	bool check;
};

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