Cod sursa(job #3217496)

Utilizator CastielGurita Adrian Castiel Data 23 martie 2024 11:24:49
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
int n,a,b,s,f1[100005],f2[100005],p,fmax1,x;
queue<int> q;
vector<int> v[100005];
int main()
{
    fin>>n;
    for(int i=1;i<=n-1;i++)
    {
        fin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    s=1;
    q.push(s);
    f1[s]=1;
    while(!q.empty())
    {
        x=q.front();
        if(fmax1<f1[x])
        {
            fmax1=f1[x];
            p=x;
        }
        for(int i=0;i<v[x].size();i++)
        {
            if(f1[v[x][i]]==0)
            {
                f1[v[x][i]]=f1[x]+1;
                q.push(v[x][i]);
            }
        }
        q.pop();
    }
    q.push(p);
    f2[p]=1;
    fmax1=0;
    while(!q.empty())
    {
        x=q.front();
        if(fmax1<f2[x])
        {
            fmax1=f2[x];
        }
        for(int i=0;i<v[x].size();i++)
        {
            if(f2[v[x][i]]==0)
            {
                f2[v[x][i]]=f2[x]+1;
                q.push(v[x][i]);
            }
        }
        q.pop();
    }
    fout<<fmax1;
    fin.close();
    fout.close();
    return 0;
}