Cod sursa(job #3339166)

Utilizator c0drinn_Rau Codrin c0drinn_ Data 6 februarie 2026 17:21:37
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
vector< int > v[100002]; // lista de vecini
  //    vf vecin

int d1[100002], d2[100000];
queue <int> q;

 void bfs(int x, int d[]){
   // d[i]==0 pt i nu stim distanta

   q.push(x);  d[x]=1;

  while ( !q.empty() ){
    int vf = q.front(); q.pop();

    int l = v[vf].size();
    for(int i = 0; i <l; i++){
      if(d[v[vf][i] ] == 0 ){ // vf---------v[vf][i]
        q.push(v[vf][i]);
        d[v[vf][i]] = d[vf]+1;
      }
    }
  }
   // q este vida



 }




int main()
{
  int n,  a, b;
  fin>>n;
  for(int i=1;i<=n-1;i++){
    fin>>a>>b; // a------b
    v[a].push_back( b );
    v[b].push_back( a );

  }

  bfs(1,d1); // d1[i]= dist minim a de la 1 la i
  // gasesc y cu d1[y] maxim

  int y=1;
  for(int i=1;i<=n;i++){
    if(d1[i]>d1[y]){
      y=i;
    }
  }

  bfs(y, d2); // d2[i]= dist minim de la y la i
  // maxim din vectorul d2

  int diam=0;
  for(int i=1;i<=n;i++){
    diam=max(diam, d2[i]);
  }

  fout<<diam;
  return 0;
}