Cod sursa(job #2787599)

Utilizator TonioAntonio Falcescu Tonio Data 23 octombrie 2021 18:56:37
Problema Parcurgere DFS - componente conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <vector>
#include <map>

using namespace std;


class GrafNeorientat
{
private:
	int nrNoduri;
	int nrMuchii;
	map <int, bool> vizitat;
	map <int, vector<int>> adiacenta;
public:
	GrafNeorientat();
	void DFS(int start);
	void NumaraCompCnx();
};

GrafNeorientat::GrafNeorientat()
{
	ifstream in("dfs.in");
	in >> this->nrNoduri;
	in >> this->nrMuchii;
	for (int i = 1; i <= nrNoduri; ++i)
		vizitat[i] = false;
	int start;
	int capat;
	for (int i = 0; i < nrMuchii; ++i)
	{
		in >> start >> capat;
		adiacenta[start].push_back(capat);
		adiacenta[capat].push_back(start);
	}
	in.close();
}

void GrafNeorientat::DFS(int start)
{
	vizitat[start] = true;
	for (int vecin : adiacenta[start])
	{
		if (!vizitat[vecin])
			DFS(vecin);
	}
}

void GrafNeorientat::NumaraCompCnx()
{
	ofstream out("dfs.out");
	int nrCompCnx = 0;
	for (int i = 1; i <= nrNoduri; ++i)
	{
		if (!vizitat[i])
		{
			DFS(i);
			nrCompCnx++;
		}
	}
		
	out << nrCompCnx;
	out.close();
}

int main()
{
	GrafNeorientat g;
	g.NumaraCompCnx();
	return 0;
}