Cod sursa(job #2972663)

Utilizator StefanL2005Stefan Leustean StefanL2005 Data 29 ianuarie 2023 22:57:20
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>

using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");

void DFS(int nod, vector< vector<int> > &Vec, vector< vector<int> > &Drum, int p, int &Max)
{
    int a = 0, b = 0, nr;

    for (int i = 0; i < Vec[nod].size(); i++)
    {
        int vecin = Vec[nod][i];

        if (vecin == p)
            continue;

        DFS(vecin, Vec, Drum, nod, Max);
        nr++;

        if (Drum[vecin][0] > a)
        {
            b = a;
            a = Drum[vecin][0];
            continue;
        }

        if (Drum[vecin][0] > b)
            b = Drum[vecin][0];
    }

    if (nr >= 2)
        Drum[nod][1] = a + b + 1;
    else
        Drum[nod][1] = 1;

    Drum[nod][0] = a + 1;

    Max = max(Drum[nod][1], Max);
}
int main()
{
    int n, Max = 0;
    in>> n;
    vector< vector<int> > Vec(n);
    vector< vector<int> > Drum(n, vector<int> (2, 0));
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        in>> a >> b; a--; b--;
        Vec[a].push_back(b);
        Vec[b].push_back(a);
    }

    /// Drum[nod][i] i = 1 --> cel mai lung lant momentan
    ///              i = 0 --> cel mai lung drum
    DFS(0, Vec, Drum, -1, Max);

    out<< Max;
    return 0;
}