Cod sursa(job #2708849)

Utilizator anadobrescuAna-Maria Dobrescu anadobrescu Data 19 februarie 2021 15:14:41
Problema Diametrul unui arbore Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
int const N=100001;
int viz[N], sf, inc, coada[N], x, y, n, maxim, imax1, imax2;
vector <int> lista[N];
int d[N];
void bfs(int nod)
{
    int i;
    viz[nod]=1;
    sf=inc=1;
    coada[inc]=nod;
    d[nod]=1;
    while(inc<=sf)
    {
        for(i=0; i<lista[coada[inc]].size(); i++)
        {
            if(viz[lista[coada[inc]][i]]==0)
            {
                sf++;
                coada[sf]=lista[coada[inc]][i];
                viz[lista[coada[inc]][i]]=1;
                d[i]=d[coada[inc]]+1;
            }
        }
        inc++;
    }
}

int main()
{
    int i;
    in>>n;
    for(i=1; i<=n-1; i++)
    {
        in>>x>>y;
        lista[x].push_back(y);
        lista[y].push_back(x);
    }
    bfs(1);
    for(i=1; i<=n; i++)
        if(d[i]>maxim)
        {
            maxim=d[i];
            imax1=i;
        }
    /*for(i=1; i<=n; i++)
    {
        viz[i]=0;
        d[i]=0;
    }*/
    bfs(imax1);
    maxim=0;
    for(i=1; i<=n; i++)
        if(d[i]>maxim)
        {
            maxim=d[i];
            imax2=i;
        }
    out<<maxim;
    return 0;
}