Cod sursa(job #3272433)

Utilizator AndreeaHzmAndreea Huzum AndreeaHzm Data 29 ianuarie 2025 13:07:24
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.71 kb
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <climits>

#define INFINIT INT_MAX

using namespace std;

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

class Graf {
private:
    int nrNoduri;
    bool eOrientat, arePonderi;
    vector<int> *adiacenta; // lista de vecini
    vector<pair<int, pair<int, int>>> muchii; // {cost, {sursa, destinatie}};

public:
    explicit Graf(int nrNoduri);

    Graf(int nrNoduri, const bool eOrientat, const bool arePonderi);

    void citire(const int nrMuchii);

    void rezolvaBFS(int &nodPlecare);

    void rezolvaDFS();

    void rezolvaBiconex();

    void rezolvaComponenteTareConexe(const int &nrMuchii);

    void havelHakimi(const bool sortareCountingSort);

    void rezolvaSortareTopologica();

    void rezolvaMuchieCritica();

    void rezolvaGrafInfoarena(int &nodStart, int &nodEnd);

    void rezolvaAPM(int &nrMuchii);

    void rezolvaDisjoint(int &nrMuchii);

    void rezolvaDijkstra(int &nrMuchii);

    void rezolvaBellmanFord(int &nrMuchii);

    vector<vector<int>> royFloyd(vector<vector<int>> &matrice);

    int rezolvaDiametruArbrore();

    ~Graf();

private:
    void adaugaMuchie(const int sursa, const int destinatie);

    void adaugaMuchiePonderat(const int sursa, const int destinatie, const int cost);

    vector<int> rezolvaBFS2(int nodPlecare);

    void BFSrecursiv(queue<int> &coada, vector<int> &vizitat);
    

};

void Graf::BFSrecursiv(queue<int> &coada, vector<int> &vizitat) {
    if (!coada.empty()) // daca mai sunt elemente in coada / nu am verificat pt toate nodurile
    {
        int nodPlecare = coada.front(); // retin nodul de unde plec
        for (auto &i: adiacenta[nodPlecare])
            if (vizitat[i] == -1) {
                // caut toate nodurile nevizitate care sunt adiacente cu nodul de plecare
                vizitat[i] = vizitat[nodPlecare] + 1; // il marcam vizitat
                coada.push(i); // il adaug in coada PUSH
            }
        coada.pop();
        BFSrecursiv(coada, vizitat);
    }
}

vector<int> Graf::rezolvaBFS2(int nodPlecare) {
    vector<int> vizitat(nrNoduri + 1, -1);
    queue<int> coada;
    coada.push(nodPlecare);
    vizitat[coada.back()] = 1;
    BFSrecursiv(coada, vizitat);
    return vizitat;
}

int Graf::rezolvaDiametruArbrore() {
    vector<int> distante = rezolvaBFS2(1);

    int diametruMaxim = -1, ultimulNod;
    for (int i = 1; i <= nrNoduri; i++)
        if (distante[i] > diametruMaxim) {
            diametruMaxim = distante[i];
            ultimulNod = i;
        }
    distante = rezolvaBFS2(ultimulNod);
    diametruMaxim = -1;
    for (int i = 1; i <= nrNoduri; i++)
        if (distante[i] > diametruMaxim)
            diametruMaxim = distante[i];
    return diametruMaxim;
}

int main() {
    int nrNoduri;
    fin >> nrNoduri;
    Graf g1(nrNoduri, false, false);
    g1.citire(nrNoduri);
    fout << g1.rezolvaDiametruArbrore();

    fin.close();
    fout.close();
    return 0;
}

Graf::Graf(const int nrNoduri) {
    this->nrNoduri = nrNoduri;
}

Graf::Graf(const int nrNoduri, const bool eOrientat, const bool arePonderi) {
    this->nrNoduri = nrNoduri;
    this->eOrientat = eOrientat;
    this->arePonderi = arePonderi;
}

void Graf::adaugaMuchie(const int sursa, const int destinatie) {
    adiacenta[sursa].push_back(destinatie);
}

void Graf::adaugaMuchiePonderat(const int sursa, const int destinatie, const int cost) {
//    adiacentaCost[sursa].push_back(muchieCost(destinatie, cost));
}

void Graf::citire(const int nrMuchii) {
    int sursa, destinatie; // extremitate muchie stanga respectiv dreapta
    adiacenta = new vector<int>[nrNoduri + 1];
    if (!arePonderi) {
        if (eOrientat)
            for (int i = 1; i <= nrMuchii; i++) {
                fin >> sursa >> destinatie;
                adaugaMuchie(sursa, destinatie);
            }
        else
            for (int i = 1; i <= nrMuchii; i++) {
                fin >> sursa >> destinatie;
                adaugaMuchie(sursa, destinatie);
                adaugaMuchie(destinatie, sursa);
            }
    } else {
        int cost; // costul muchiei
        muchii.resize(nrMuchii + 1);
        if (eOrientat)
            for (int i = 1; i <= nrMuchii; i++) {
                fin >> sursa >> destinatie >> cost;
                muchii[i] = {cost, {sursa, destinatie}};
            }
        else
            for (int i = 1; i <= nrMuchii; i++) {
                fin >> sursa >> destinatie >> cost;
                muchii[i] = {cost, {sursa, destinatie}};
            }
    }
}

Graf::~Graf() {
    delete[] adiacenta;
}