Cod sursa(job #815404)

Utilizator moscaliuc_ovidiuMoscaliuc Ovidiu moscaliuc_ovidiu Data 16 noiembrie 2012 22:07:31
Problema Parcurgere DFS - componente conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>

#define MAX_N		100001

class Node
{
public:
	int color;
	std::vector<int> neighbours;
};

Node Graf[MAX_N];

void dfs(int _node, int _color)
{
	Graf[_node].color = _color;

	for (int i = 0; i < Graf[_node].neighbours.size(); ++ i)
		if (Graf[Graf[_node].neighbours[i]].color == 0)
			dfs(Graf[_node].neighbours[i], _color);
}

int main()
{
	std::ifstream fin("dfs.in");
	std::ofstream fout("dfs.out");

	int N, M, x, y;

	fin>>N>>M;

	while(M--)
	{
		fin>>x>>y;

		Graf[x].neighbours.push_back(y);
		Graf[y].neighbours.push_back(x);
	}

	bool bFound = true;
	int color = 0;

	while(bFound)
	{
		bFound = false;
		for (x = N; x > 0; -- x)
		{
			if (Graf[x].color == 0)
			{
				bFound = true;
				break;
			}
		}

		if (bFound)
			dfs(x, ++ color);
	}

	fout<<color;
		
	return 0;
}