Cod sursa(job #3272427)

Utilizator AndreeaHzmAndreea Huzum AndreeaHzm Data 29 ianuarie 2025 13:01:33
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.63 kb
#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;
}