Pagini recente » Cod sursa (job #2483801) | Cod sursa (job #645325) | Cod sursa (job #997248) | Cod sursa (job #646198) | Cod sursa (job #3272427)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
class Graf {
private:
int nrNoduri;
vector<int> *adiacenta; // Lista de adiacență pentru arbore
public:
explicit Graf(int nrNoduri);
void citire(const int nrMuchii);
int rezolvaDiametruArbore();
~Graf();
private:
vector<int> rezolvaBFS(int nodPlecare);
};
// Constructor: Inițializează numărul de noduri și lista de adiacență
Graf::Graf(const int nrNoduri) {
this->nrNoduri = nrNoduri;
adiacenta = new vector<int>[nrNoduri + 1];
}
// Destructor: Eliberează memoria alocată dinamic
Graf::~Graf() {
delete[] adiacenta;
}
// Citește arborele din fișier și construiește lista de adiacență
void Graf::citire(const int nrMuchii) {
int sursa, destinatie;
for (int i = 1; i < nrMuchii; i++) { // Un arbore are (N-1) muchii
fin >> sursa >> destinatie;
adiacenta[sursa].push_back(destinatie);
adiacenta[destinatie].push_back(sursa);
}
}
// Parcurgere BFS pentru a calcula distanțele de la un nod dat
vector<int> Graf::rezolvaBFS(int nodPlecare) {
vector<int> distanta(nrNoduri + 1, -1); // Inițial, toate distanțele sunt -1 (noduri nevizitate)
queue<int> coada;
coada.push(nodPlecare);
distanta[nodPlecare] = 0; // Distanța față de sine este 0
while (!coada.empty()) {
int nod = coada.front();
coada.pop();
for (auto vecin: adiacenta[nod]) {
if (distanta[vecin] == -1) { // Dacă nodul nu a fost vizitat
distanta[vecin] = distanta[nod] + 1;
coada.push(vecin);
}
}
}
return distanta;
}
// Funcție pentru determinarea diametrului arborelui
int Graf::rezolvaDiametruArbore() {
vector<int> distante = rezolvaBFS(1); // Primul BFS din nodul 1
// Găsim nodul cel mai îndepărtat de nodul 1
int nodMaxim = 1, distMax = -1;
for (int i = 1; i <= nrNoduri; i++)
if (distante[i] > distMax) {
distMax = distante[i];
nodMaxim = i;
}
// Al doilea BFS din nodul cel mai îndepărtat
distante = rezolvaBFS(nodMaxim);
distMax = -1;
for (int i = 1; i <= nrNoduri; i++)
if (distante[i] > distMax)
distMax = distante[i];
return distMax; // Diametrul arborelui
}
int main() {
int nrNoduri;
fin >> nrNoduri;
Graf g1(nrNoduri);
g1.citire(nrNoduri);
fout << g1.rezolvaDiametruArbore();
fin.close();
fout.close();
return 0;
}