Cod sursa(job #2550713)

Utilizator MarcGrecMarc Grec MarcGrec Data 19 februarie 2020 08:25:46
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#define MAX_N 100000

#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

int n, rasp, Dmax[MAX_N + 1];
vector<int> G[MAX_N + 1];

void Df(int nod);

int main()
{
    fin >> n;
    for (int i = 0, x, y; i < (n - 1); ++i)
    {
        fin >> x >> y;
        G[x].push_back(y);
    }

    Df(1);

    fout << rasp + 1;

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

void Df(int nod)
{
    for (int vecin : G[nod])
    {
        Df(vecin);
        Dmax[nod] = max(Dmax[nod], 1 + Dmax[vecin]);
    }

    bool ok = false;
    for (int vecin : G[nod])
    {
        if ((1 + Dmax[vecin]) == Dmax[nod])
        {
            if (ok)
            {
                rasp = max(rasp, 1 + Dmax[vecin] + Dmax[nod]);
            }
            else
            {
                ok = true;
            }
        }
        else
        {
            rasp = max(rasp, 1 + Dmax[vecin] + Dmax[nod]);
        }
    }
}