Cod sursa(job #2310492)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 31 decembrie 2018 19:05:57
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
/// TONI BO$$ was here
/// #MLC

using namespace std;

vector <int> G[101001];
int f[101001];

void bfs(int i)
{
    queue <int> q;
    f[i]=1;
    q.push(i);
    while(!q.empty())
    {
        int z=q.front();
        q.pop();
        for(auto it : G[z])
            if(!f[it])
            {
                f[it]=f[z]+1;
                q.push(it);
            }
    }
}

int main()
{
    int t,n,m,x,y,i,p,maxdist;
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    scanf("%d",&n);
    for(i=1; i<n; i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(i=1; i<=n; i++)
        f[i]=0;
    bfs(1);
    p=0,maxdist=0;
    for(i=2; i<=n; i++)
        if(maxdist<f[i])
        {
            maxdist=f[i];
            p=i;
        }
    for(i=1; i<=n; i++)
        f[i]=0;
    bfs(p);
    maxdist=0;
    for(i=1; i<=n; i++)
        if(i!=p && maxdist<f[i])
            maxdist=f[i];
    printf("%d\n",maxdist);
    for(i=1; i<=n; i++)
        G[i].clear();

    return 0;
}