Cod sursa(job #2708826)

Utilizator vlad_dimuVlad Dimulescu vlad_dimu Data 19 februarie 2021 14:53:36
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>
#define MAXN 100000
using namespace std;

ifstream fin( "darb.in" );
ofstream fout( "darb.out" );

vector <int> lista[MAXN + 1];
int viz[MAXN + 1], coada[MAXN + 1], n;
int L[MAXN + 1];

void bfs( int x ){
  int st, dr, i, dist;
  viz[x] = 1;
  st = dr = 1;
  coada[st] = x;
  L[x] = 1;
  while( st <= dr ){
    dist = L[coada[st]];
    for( i = 0; i < lista[coada[st]].size(); i++ ){
      if(viz[lista[coada[st]][i]] == 0 ){
        dr++;
        coada[dr] = lista[coada[st]][i];
        viz[lista[coada[st]][i]] = 1;
        L[lista[coada[st]][i]] = dist + 1;
      }
    }
    st++;
  }
}

int main(){
  int i, n1, n2, maxim, frunza;
  fin >> n;
  for( i = 1; i <= n - 1; i++ ){
    fin >> n1 >> n2;
    lista[n1].push_back(n2);
    lista[n2].push_back(n1);
  }
  bfs(1);
  //cautam maximul, adica cea mai departata frunza
  maxim = 0;
  frunza = 1;
  for( i = 1; i <= n; i++ ){
    if( L[i] > maxim ){
      maxim = L[i];
      frunza = i;
    }
    viz[i] = L[i] = 0;
  }
  bfs(frunza);
  maxim = 0;
  for( i = 1; i <= n; i++ )
    if( L[i] > maxim )
      maxim = L[i];
  fout << maxim;
  return 0;
}