Cod sursa(job #1141629)

Utilizator TwoOfDiamondsDaniel Alexandru Radu TwoOfDiamonds Data 12 martie 2014 23:58:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <vector>

using namespace std;

class DFS
{
private:
	struct node
	{
		vector<int> vecini;
		bool vizitat;
	} *noduri;

	int nrNoduri, nrMuchii;

public:
	DFS();
	int compConexe();

private:
	void parcurgeDFS(int i);
};

void DFS::parcurgeDFS(int i)
{
	noduri[i].vizitat = true;
	for (auto& it : noduri[i].vecini)
		if (noduri[it].vizitat == false) parcurgeDFS(it);
}

int DFS::compConexe()
{
	int componente = 0;

	for (int i = 1; i <= nrNoduri; i++)
		if(!noduri[i].vizitat)
			parcurgeDFS(i), componente++;

	return componente;
}

DFS::DFS()
{
	ifstream IN("dfs.in");

	IN >> nrNoduri >> nrMuchii;

	noduri = new node[nrNoduri + 1];

	for (int i = 1; i <= nrNoduri; i++)
		noduri[i].vizitat = false;

	for (int i = 1 ; i <= nrMuchii; i++)
	{
		int x, y;
		IN >> x >> y;
		noduri[x].vecini.push_back(y);
		noduri[y].vecini.push_back(x);
	}

	IN.close();
}

int main()
{
	DFS graf;
	ofstream OUT("dfs.out");
	OUT << graf.compConexe();
	OUT.close();
	return 0;
}