Cod sursa(job #2023217)

Utilizator UWantMyNameGheorghe Vlad Camil UWantMyName Data 18 septembrie 2017 16:18:37
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
#define in "darb.in"
#define out "darb.out"
using namespace std;
ifstream fin(in);
ofstream fout(out);

int n;
int d[100003];
vector <int> L[100003];


void Citire()
{
    int i,j;

    fin >> n;
    while (fin >> i >> j)
    {
        L[i].push_back(j);
        L[j].push_back(i);
    }
}

void DFS(int k)
{
    for (auto i : L[k])
        if (d[i] == 0)
        {
            d[i] = d[k] + 1;
            DFS(i);
        }
}

void Rezolvare()
{
    int i,p = 1;

    d[1] = 1;
    DFS(1);

    /// aflu nodul cu d[i] maxim
    for (i = 2; i <= n; i++)
        if (d[i] > d[p]) p = i;


    ///golesc d-ul
    for (i = 1; i <= n; i++)
        d[i] = 0;

    d[p] = 1;
    DFS(p);

    /// aflu nodul cu d[i] maxim (frunza)
    p = 1;
    for (i = 2; i <= n; i++)
        if (d[i] > d[p]) p = i;

    fout << d[p] << "\n";
}

int main()
{
    Citire();
    Rezolvare();

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