Cod sursa(job #2972996)

Utilizator StefanL2005Stefan Leustean StefanL2005 Data 30 ianuarie 2023 19:47:32
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 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<int> &D, int p)
{
    if (p == -1)
        D[nod] = 1;
    else
        D[nod] = D[p] + 1;

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

        DFS(Vec[nod][i], Vec, D, nod);
    }
}
int main()
{
    int n, l = 0;
    in>> n;
    vector< vector<int> > Vec(n);

    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);
    }

    vector<int> D(n, 0);
    vector<int> Dfinal(n, 0);

    DFS(0, Vec, D, -1);

    for (int i = 0; i < n; i++)
        if (D[i] > D[l])
            l = i;

    DFS(l, Vec, Dfinal, -1);

    for (int i = 0; i < n; i++)
        if (Dfinal[i] > Dfinal[l])
            l = i;

    out<< Dfinal[l];
    return 0;
}