Cod sursa(job #2795375)

Utilizator lucriLuchian Cristian lucri Data 6 noiembrie 2021 11:56:31
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
int n,x,y,r,d[100010],dmax,pmax;
bool t[100010];
vector<vector<int>>a;
queue<int>c;
int main()
{
    in>>n;
    a.resize(n+5);
    for(int i=1;i<n;++i)
    {
        in>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    c.push(1);
    t[1]=true;
    d[1]=1;
    while(!c.empty())
    {
        x=c.front();
        c.pop();
        for(auto w:a[x])
        {
            if(t[w]==false)
            {
                t[w]=true;
                d[w]=d[x]+1;
                c.push(w);
                if(d[w]>dmax)
                {
                    dmax=d[w];
                    pmax=w;
                }
            }
        }
    }
    for(int i=1;i<=n;++i)
    {
        t[i]=false;
        d[i]=0;
    }
    c.push(pmax);
    t[pmax]=true;
    d[pmax]=1;
    while(!c.empty())
    {
        x=c.front();
        c.pop();
        for(auto w:a[x])
        {
            if(t[w]==false)
            {
                t[w]=true;
                d[w]=d[x]+1;
                c.push(w);
                if(d[w]>dmax)
                {
                    dmax=d[w];
                }
            }
        }
    }
    out<<dmax;
    return 0;
}