Cod sursa(job #3239191)

Utilizator Sasha_12454Eric Paturan Sasha_12454 Data 2 august 2024 19:13:36
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

std :: ifstream in ("darb.in");

std :: ofstream out ("darb.out");

const int NMAX = 1e5 + 5;

const int INF = 1e6;

int n;

int x;

int y;

int maxi;

int ind;

int dist[NMAX];

std :: vector <int> v[NMAX];

std :: bitset <NMAX> visited;

void dfs(int nod)
{
    for(int i : v[nod])
    {
        if(dist[nod] + 1 < dist[i])
        {
            dist[i] = dist[nod] + 1;

            dfs(i);
        }
    }
}

int main()
{

    in >> n;

    for(int i = 1; i < n; i ++)
    {
        in >> x >> y;

        v[x].push_back(y);

        v[y].push_back(x);
    }

    for(int i = 1; i <= n; i ++)
    {
        dist[i] = INF;
    }

    dist[1] = 0;

    dfs(1);

    for(int i = 1; i <= n; i ++)
    {
        if(dist[i] > maxi)
        {
            maxi = dist[i];

            ind = i;
        }
    }

    for(int i = 1; i <= n; i ++)
    {
        dist[i] = INF;
    }

    dist[ind] = 0;

    maxi = 0;

    dfs(ind);

    for(int i = 1; i <= n; i ++)
    {
        maxi = std :: max(maxi, dist[i]);
    }

    out << maxi + 1;

    return 0;
}