Cod sursa(job #2787614)

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

using namespace std;

const int noduriMAX = 100001;

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

GrafNeorientat::GrafNeorientat()
{
	ifstream in("dfs.in");
	in >> nrNoduri;
	in >> nrMuchii;
	for (int i = 1; i <= nrNoduri; ++i)
		vizitat[i] = false;
	int start;
	int capat;
	adiacenta.resize(nrNoduri + 1);
	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;
}