Cod sursa(job #2611914)

Utilizator cpopescu1Popescu Cristian cpopescu1 Data 7 mai 2020 20:16:21
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
#define maxn 100005
#define fopen ifstream
#define fclose ofstream
using namespace std;

fopen fin("darb.in");
fclose fout("darb.out");

int n;
vector<int> lista[maxn];
int D[maxn];

void read()
{
    fin>>n;
    int x,y;
    for(int i=1;i<n;i++){
        fin>>x>>y;
        lista[x].push_back(y);
        lista[y].push_back(x);
    }
}

void dfs(int nod,int dist,int D[])
{
    if(D[nod]!=-1)
        return;
    D[nod]=dist; //salvez distantele de la fiecare nod la radacina

    for(auto x:lista[nod])
        dfs(x,dist+1,D);
}

void init()
{
    for(int i=1;i<=n;i++) D[i]=-1;
}

int main()
{
    read();
    init();
    dfs(1,1,D);
    int x=1;
    for(int i=2;i<=n;i++)
        if(D[i]>D[x])
            x=i;
    init();
    dfs(x,1,D);
    int sol=D[1];
    for(int i=2;i<=n;i++){
        if(D[i]>sol)
            sol=D[i];
    }
    fout<<sol;
    return 0;
}