Cod sursa(job #2814058)

Utilizator amalia.gemanGeman Aamalia amalia.geman Data 7 decembrie 2021 15:22:33
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <bits/stdc++.h>
#define NMax 100001


using namespace std;

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


class graf
{
    int nrNoduri, nrMuchii;
    bool orientat;
    vector <int> gr[NMax]; // liste de adiacenta ale grafului

public:
    graf(int n, int m, bool o); // constructor
    void Citire_Arbore();

    // Diametrul unui arbore
    void Diametru_Arbore();
    void BFS_Diametru_Arbore(int s, int &ultim, int &distanta_maxima);
};


int N, M;

graf :: graf(int n, int m, bool o)
{
    nrNoduri = n;
    nrMuchii = m;
    orientat = o;
}

void graf :: Citire_Arbore()
{
    for(int i = 1; i <= nrMuchii; ++i)
    {
        int x, y;
        fin >> x >> y;
        gr[x].push_back(y);
        gr[y].push_back(x);
    }
}

void graf :: BFS_Diametru_Arbore(int s, int &capat, int &distanta_maxima)
{
    int distanta[NMax];
    queue <int> q;
    bool viz[NMax] = {0};

    viz[s] = 1;
    distanta[s] = 1;
    q.push(s);

    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        for(auto i : gr[k])
            if(!viz[i])
            {
                viz[i] = 1;
                q.push(i);
                distanta[i] = distanta[k] + 1;
            }
    }

    distanta_maxima = 0;
    for(int i = 1; i<= nrNoduri; ++i)
        if(distanta[i] > distanta_maxima)
        {
            distanta_maxima = distanta[i];
            capat = i;
        }
}

void graf :: Diametru_Arbore()
{
    int capat1, capat2, distanta_maxima;

    BFS_Diametru_Arbore(1, capat1, distanta_maxima);
    BFS_Diametru_Arbore(capat1, capat2, distanta_maxima);

    fout << distanta_maxima;
}


int main()
{
    fin >> N;
    graf G(N, N-1, 0); // arbore
    G.Citire_Arbore();
    G.Diametru_Arbore();

    return 0;
}