Cod sursa(job #1438049)

Utilizator VladutZ94FMI Chichirau Vlad Vasile VladutZ94 Data 18 mai 2015 22:57:12
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <iostream>
#include <fstream>
#include <vector>


class Graf
{
private:
	std::vector< std::vector<int> > adiacenta;
	int n, m;
	std::vector<bool> vizit;
public:
	Graf();
	Graf(int n, int m);
	int get_n(){ return n; }
	int get_m(){ return m; }
	bool vizitat(int i);
	void citire();
	void afisare();
	void DFS_conexe(int nod);

};

Graf::Graf()
{

}

Graf::Graf(int n, int m)
{
	this->adiacenta.resize(n + 1);
	this->vizit.resize(n + 1, false);
	this->n = n;
	this->m = m;
}

bool Graf::vizitat(int i)
{
	if (this->vizit[i] == true)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void Graf::citire()
{
	int x, y;
	std::ifstream f("dfs.in");
	f >> x >> y;
	for (int i = 0; i <= this->get_m(); i++)
	{
		f >> x >> y;
		this->adiacenta[x].push_back(y);
	}
}

void Graf::afisare()
{
	std::ofstream g("dfs.out");
	for (int i = 0; i <= this->get_n(); i++)
	{
		for (int j = 0; j < this->adiacenta[i].size(); j++)
		{
			g << i << " " << this->adiacenta[i][j] << "\n";
		}
	}
}

void Graf::DFS_conexe(int nod)
{
	this->vizit[nod] = true;
	int aux;
	for (int i = 0; i < this->adiacenta[nod].size(); i++)
	{
		aux = this->adiacenta[nod][i];
		if (this->vizit[aux] == false)
		{
			DFS_conexe(aux);
		}
	}
}

int n, m;

int main()
{

	std::ifstream f("dfs.in");
	std::ofstream g("dfs.out");

	f >> n >> m;
	Graf graf(n, m);
	graf.citire();
	int contor = 0;
	for (int i = 1; i <= n; i++)
	{
		if (graf.vizitat(i) == false)
		{
			contor++;
			graf.DFS_conexe(i);
		}
	}
	g << contor;

	return 0;
}