Cod sursa(job #2812025)

Utilizator ptr22222Petru Popescu ptr22222 Data 3 decembrie 2021 19:30:46
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.22 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

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

const int nmax = 100001;
const int inf = 1<<30;
class Graf
{
private:
    bool orientat;
    int nrNoduri;
    vector <int> listaAdiacenta[nmax];
    vector <pair <int, int>> listaAdiacentaCost[nmax];
public:
    Graf(int nrNoduri = 0, bool orientat = false);
    void adaugaMuchie(int, int);
    void adaugaMuchieCost(int, int, int);
    void citireMuchii(int);
    void citireMuchiiCost(int);
    vector<int> BFS(int);
    void DFS(int, bool*);
    int nrComponenteConexe();
    void DFSStiva(int nodcurent, bool *, stack<int> &);
    void sortareTopologica();
    void TarjanCTC(int&, int, int*, int*, bool*, stack <int> &, vector<vector<int>> &);
    void CTC();
    void TarjanBC(int&, int, int, int*, int*, stack <int>&, vector<vector<int>>&);
    void BC();
    void TarjanMC(int&, int, int, int*, int*, vector<pair<int,int>>&);
    void MC();
    vector <int> citireHakimi();
    bool Hakimi(vector <int>);
    vector <int> Dijkstra(int);
    pair<int, vector <pair <int, int>>> Prim(int);
    vector <int> BellmanFord(int);
    void reuniune(int, int, vector<int>&, vector<int>&);
    int gasire(int, vector<int>&);
    void verifica(int, int, vector<int>&);
    void paduri();
    int diametru();
};

Graf :: Graf(int nrNoduri, bool orientat) : nrNoduri(nrNoduri), orientat(orientat)
{
    this->nrNoduri = nrNoduri;
    this->orientat = orientat;
}

void Graf:: adaugaMuchie(int nod1, int nod2)
{
    listaAdiacenta[nod1].push_back(nod2);
}

void Graf::citireMuchii(int nrMuchii)
{
    int nod1, nod2;
    for(int i = 0; i < nrMuchii; i++)
    {
        in >> nod1 >> nod2;
        listaAdiacenta[nod1].push_back(nod2);
        if(!orientat)
        {
            listaAdiacenta[nod2].push_back(nod1);
        }
    }
}

vector<int> Graf::BFS(int start)
{
    queue <int> coadaBFS;
    int vizitatBFS[nmax] = {false};
    vector <int> distantaBFS(nmax);
    fill(distantaBFS.begin(), distantaBFS.end(), 0);
    coadaBFS.push(start);
    vizitatBFS[start] = true;
    distantaBFS[start] = 1;
    while(!coadaBFS.empty())
    {
        int nodCurent = coadaBFS.front();
        coadaBFS.pop();
        for(auto vecin:listaAdiacenta[nodCurent])
        {
            if(!vizitatBFS[vecin])
            {
                vizitatBFS[vecin] = true;
                distantaBFS[vecin] = distantaBFS[nodCurent] + 1;
                coadaBFS.push(vecin);
            }
        }
    }
    return distantaBFS;
}

int Graf::diametru()
{
    vector <int> distante(nmax);
    distante = BFS(1);
    int distantaMaxima = -1, nodMaxim;
    for(int i = 1; i <= nrNoduri; i++)
    {
        if(distante[i] > distantaMaxima)
        {
            distantaMaxima = distante[i];
            nodMaxim = i;
        }
    }
    distante = BFS(nodMaxim);
    distantaMaxima = -1;
    for(int i = 1; i <= nrNoduri; i++)
    {
        if(distante[i] > distantaMaxima)
        {
            distantaMaxima = distante[i];
        }
    }
    return distantaMaxima;
}

int main() {
    int n, m;
    in >> n;
    Graf g(n,false);
    g.citireMuchii(n - 1);
    int rezultat = g.diametru();
    out << rezultat;
    return 0;
}