Cod sursa(job #2999505)

Utilizator AndreiStreheStreche Andrei Claudiu AndreiStrehe Data 11 martie 2023 09:15:27
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

#define nmax 100001
vector <int> a[nmax];
queue <int> coada;

int nodcurent,vecin,maxim,fmax,n,i,j,k1,k2,m1;
int d[nmax];

void dfs()
{

    while(coada.empty()==0)
    {
        nodcurent=coada.front(); coada.pop();
        for(unsigned int i=0; i<a[nodcurent].size();i++)
        {
            vecin=a[nodcurent][i];
            if(d[vecin]==0)
            {
                d[vecin]=d[nodcurent]+1;
                coada.push(vecin);
                if(d[vecin]>maxim)
                {
                    maxim=d[vecin];
                    fmax=vecin;
                }
            }
        }

    }
}

int main()
{
    f>>n;
    for(i=1;i<n;i++)
    {
        f>>k1>>k2;
        a[k1].push_back(k2);
        a[k2].push_back(k1);
    }

    coada.push(1);

    dfs();
    for(i=1;i<=n;i++)
        d[i]=0;

    m1=maxim; maxim=0;
    coada.push(fmax);
    dfs();

    g<<maxim+1;

    return 0;
}