Cod sursa(job #2812675)

Utilizator loraclorac lorac lorac Data 4 decembrie 2021 21:41:34
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
const int lim=1e5+4;
const int inf=1e9+7;
vector<int> vec[lim];
int dist[lim];
bool ok[lim];
queue<int> q;
int n,x,y;
int main()
{
    in>>n;
    for(int i=1;i<n;++i)
        in>>x>>y,
        vec[x].push_back(y),
        vec[y].push_back(x);
    for(int i=1;i<=n;++i)
        dist[i]=inf;
    dist[1]=0;
    int last;
    q.push(1);
    ok[1]=true;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        last=x;
        for(int y:vec[x])
        if(!ok[y])
        {
            dist[y]=dist[x]+1;
            ok[y]=true;
            q.push(y);
        }
    }
    for(int i=1;i<=n;++i)
        ok[i]=0,
        dist[i]=inf;
    dist[last]=0;
    q.push(last);
    ok[last]=true;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        last=x;
        for(int y:vec[x])
        if(!ok[y])
        {
            dist[y]=dist[x]+1;
            ok[y]=true;
            q.push(y);
        }
    }
    out<<dist[last]+1<<'\n';
    return 0;
}