Cod sursa(job #2454922)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 10 septembrie 2019 11:24:38
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
vector <int> v[100001];
int niv[100001],coada[100001],ultim,diametru;
void bfs(int primul)
{
    for(int i=1;i<=100000;i++)
        niv[i]=0;
    int p=0,u=-1;
    coada[++u]=primul;
    niv[primul]=1;
    while(p<=u)
    {
        for(int i=0; i<v[coada[p]].size(); i++)
            if(!niv[v[coada[p]][i]])
            {
                niv[v[coada[p]][i]]=niv[coada[p]]+1;
                coada[++u]=v[coada[p]][i];
            }
        p++;
    }
    ultim=coada[u];
    diametru=niv[coada[u]];
}
int main()
{
    int n,i,a,b;
    in>>n;
    for(i=1; i<=n-1; i++)
    {
        in>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    bfs(1);
    bfs(ultim);
    out<<diametru;
    return 0;
}