Cod sursa(job #2793717)

Utilizator AlexCrpCarpineanu Alexandru AlexCrp Data 3 noiembrie 2021 22:07:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.58 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

class Graf
{
private:

	int nrMuchii, nrNoduri;
	vector<vector<int>> listaAdiacenta;
	bool orientat;

	void adaugaMuchie(int, int, bool);		//Am decis sa fac adaugarea unei muchii in lista de adiacenta o functie, poate o sa fie useful later?
	void DFS(int, vector<bool>&);

public:
	Graf();
	Graf(int, int, bool);
	void BFS(int);							//Functie care rezolva problema BFS de pe infoarena
	int DFSrezolvare(int);
};

Graf::Graf()
{
	nrMuchii = 0;
	nrNoduri = 0;
	orientat = false;
}

Graf::Graf(int n, int m, bool orr)
{
	int x, y;

	nrNoduri = n;
	nrMuchii = m;
	orientat = orr;
	listaAdiacenta.resize(nrNoduri + 1);	//Construim si reprezentarea grafului in constructor

	for (int i = 0; i < nrMuchii; i++)
	{
		fin >> x >> y;
		adaugaMuchie(x, y, orientat);
	}
}

void Graf::adaugaMuchie(int n1, int n2, bool orr)
{
	listaAdiacenta[n1].push_back(n2);
	if (!orr)
	{
		listaAdiacenta[n2].push_back(n1);
	}
}

void Graf::BFS(int nodStart)
{
	queue<int> q;
	vector<bool> vizitate(nrNoduri+1, false);		//vector de bool initializat cu false, in el vom retine daca nodurile au fost vizitate
	vector<int> distante(nrNoduri+1, -1);			//vector de int care retine distantele de la nodul de start, initializat cu -1

	q.push(nodStart);

	vizitate[nodStart] = true;
	distante[nodStart] = 0;

	while (!q.empty())
	{
		int nodCurent = q.front();
		q.pop();

		for (int nodVecin : listaAdiacenta[nodCurent])
		{
			if (!vizitate[nodVecin])
			{
				vizitate[nodVecin] = true;			//BFS normal, iar in if() calculam si distanta dintre nodul curent si nodul de start
				q.push(nodVecin);					//Distanta creste cu 1 de fiecare data cand trecem de la un nod la altul
				distante[nodVecin] = distante[nodCurent] + 1;
			}
		}
	}

	for (int i=1; i < distante.size(); i++)
	{
		fout << distante[i] << ' ';					//Afisam distantele
	}
}

void Graf::DFS(int nodStart, vector<bool>& vizitate)
{
	vizitate[nodStart] = true;
	for (int i : listaAdiacenta[nodStart])
	{
		if (!vizitate[i])
		{
			DFS(i, vizitate);
		}
	}
	
}

int Graf::DFSrezolvare(int nodStart)
{
	vector<bool> vizitate(nrNoduri+1, false);
	int nrComponente = 0;
	
	for (int i = 1; i < vizitate.size(); i++)
	{
		if (!vizitate[i])
		{
			DFS(i, vizitate);
			nrComponente++;
		}
	}
	return nrComponente;
}

int main()
{
	int n, m, rez=0;

	fin >> n >> m;

	Graf G(n, m, false);

	fout << G.DFSrezolvare(1);

	return 0;
}