Cod sursa(job #2427575)

Utilizator PrekzursilAndrei Visalon Prekzursil Data 1 iunie 2019 00:03:52
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int ans[100005], xmax, rs, i, n, x, y;
vector <int> v[100005];
void bfs(int nod)
{
    queue<int> q;
    q.push(nod);
    for(int i=0;i<=n;i++)
        ans[i]=-1;
    ans[nod]=0;
    xmax=0;
    rs=nod;
    while(!q.empty())
    {
        int aux=q.front();
        for(int i=0;i<v[aux].size();i++)
            if(ans[v[aux][i]]==-1)
        {
            ans[v[aux][i]]=ans[aux]+1;
            if(ans[v[aux][i]]>xmax)
            {
                xmax=ans[v[aux][i]];
                rs=v[aux][i];
            }
            q.push(v[aux][i]);
        }
        q.pop();
    }
}
int main()
{
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        v[x].pb(y);
        v[y].pb(x);
    }
    bfs(1);
    bfs(rs);
    printf("%d\n",xmax+1);
    return 0;
}