Cod sursa(job #2741710)

Utilizator FrostShadowEusebiu-Mihai Burtescu FrostShadow Data 18 aprilie 2021 09:35:22
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include<fstream>
#include<iostream>
#include<vector>
#include<deque>
#include<cstring>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
int n,x,y,dmax,dpoz;
vector<int> L[100005];
int d[100005];
void bfs(int nod)
{
    memset(d,0,sizeof(d));
    deque<int> q;
    q.push_back(nod);
    d[nod]=1;
    while(!q.empty())
    {
        nod=q.front();
        q.pop_front();
        for(int i=0;i<L[nod].size();++i)
        {
            int vecin=L[nod][i];
            if(d[vecin]==0)
            {
            d[vecin]=d[nod]+1;
            q.push_back(vecin);
            }
        }
    }
}
int main()
{
    fin>>n;
    for(int i=1;i<=n-1;++i)
    {
        fin>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
    bfs(1);
    for(int i=1;i<=n;++i)
    {
        if(d[i]>dmax)
        {
            dmax=d[i];
            dpoz=i;
        }
    }
    bfs(dpoz);
    for(int i=1;i<=n;++i)
    {
        if(d[i]>dmax)
        {
            dmax=d[i];
        }
    }
    fout<<dmax;

}