Cod sursa(job #3214802)

Utilizator MerlinTheWizardMelvin Abibula MerlinTheWizard Data 14 martie 2024 14:26:19
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include<bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

const int NMAX = 1e5 + 5;
int n, dist[NMAX], max1, maxnode;
vector<int> v[NMAX];

void dfs(int node)
{
    for(auto u : v[node])
    {
        if(!dist[u])
        {
            dist[u] = dist[node] + 1;
            dfs(u);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);

    int a, b;
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    dist[1] = 1;
    dfs(1);
    
    for(int i = 1; i <= n; i++)
        if(max1 < dist[i])
        {
            max1 = dist[i];
            maxnode = i;
        }
    
    memset(dist, 0, sizeof(dist));
    dist[maxnode] = 1;
    dfs(maxnode);

    max1 = 0;
    for(int i = 1; i <= n; i++)
        max1 = max(max1, dist[i]);
    
    cout << max1;
}