Cod sursa(job #2769631)

Utilizator CelestinNegraru Celestin Celestin Data 16 august 2021 22:14:37
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <queue>
#define maxi 100000
using namespace std;
ifstream f;
ofstream g;
queue<int> coada;
vector<int> V[1+maxi];
int n,D1[1+maxi],D2[1+maxi],max1,nextt;
bool viz[1+maxi];
void READ()
{
    int a,b;
    f.open("darb.in",ios::in);
    f>>n;
    for(int i=1;i<=n-1;i++)
    {
        f>>a>>b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
    f.close();
    return;
}
void INIT()
{
    for(int i=1;i<=n;i++)
        viz[i]=false;
    return;
}
void BFS(int x,int D[])
{
    coada.push(x);
    while(!coada.empty())
    {
        int sursa=coada.front();
        viz[sursa]=true;
        coada.pop();
        for(auto a:V[sursa])
        {
            if(!viz[a])
            {
                D[a]=D[sursa]+1;
                coada.push(a);
            }
        }
    }
    return;
}
int main()
{
    g.open("darb.out",ios::out);
    READ();
    BFS(1,D1);
    for(int i=1;i<=n;i++)
        if(D1[i]>max1)
         max1=D1[i],nextt=i;
    INIT();
    BFS(nextt,D2);
    for(int i=1;i<=n;i++)
        if(D2[i]>max1)
            max1=D2[i];
    g<<max1+1;
    g.close();
    return 0;
}