Cod sursa(job #3296075)

Utilizator pachy2007Pachitanu Matei pachy2007 Data 11 mai 2025 10:36:40
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
vector<int>v[100002];
int dist[100002];
priority_queue<int>pq;
int n,a,b;
int maxi,maxim;
int main()
{
    fin>>n;
    for(int i=1;i<n;i++)
    {
        fin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for(int i=1;i<=n;i++)
        dist[i]=1e9;
    pq.push(1);
    dist[1]=0;
    while(!pq.empty())
    {
        int c=pq.top();
        pq.pop();
        for(auto next:v[c])
        {
            if(dist[next]>dist[c]+1)
            {
                dist[next]=dist[c]+1;
                pq.push(next);
                if(dist[next]>maxi){maxi=dist[next];
                                   maxim=next;}
            }
        }
    }

    for(int i=1;i<=n;i++)
        dist[i]=1e9;
    pq.push(maxim);
    dist[maxim]=0;
    maxi=0;
    maxim=0;
    while(!pq.empty())
    {
        int c=pq.top();
        pq.pop();
        for(auto next:v[c])
        {
            if(dist[next]>dist[c]+1)
            {
                dist[next]=dist[c]+1;
                pq.push(next);
                if(dist[next]>maxi){maxi=dist[next];
                                   maxim=next;}
            }
        }
    }
    fout<<maxi+1;
    return 0;
}