Cod sursa(job #2861473)

Utilizator vladburacBurac Vlad vladburac Data 4 martie 2022 00:32:44
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int NMAX = 1e5;

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

vector <int> edges[NMAX];
int dist[NMAX];
int n;
queue <int> q;

void bfs( int node ) {
  int i;
  for( i = 0; i < n; i++ )
    dist[i] = 0;
  q.push( node );
  dist[node] = 1;
  while( !q.empty() ) {
    int qfront = q.front();
    q.pop();
    for( auto neighbour: edges[qfront] ) {
      if( !dist[neighbour] ) {
        q.push( neighbour );
        dist[neighbour] = dist[qfront] + 1;
      }
    }
  }
}
int main() {
  int i, x, y, poz;
  fin >> n;
  for( i = 0; i < n - 1; i++ ) {
    fin >> x >> y;
    x--;
    y--;
    edges[x].push_back( y );
    edges[y].push_back( x );
  }
  /*for( i = 0; i < n; i++ ) {
    for( auto j: edges[i] )
      cout << j << " ";
    cout << endl;
  }*/
  bfs( 0 );
  int dmax = 0;
  for( i = 0; i < n; i++ ) {
    if( dist[i] > dmax ) {
      dmax = dist[i];
      poz = i;
    }
  }
  bfs( poz );
  dmax = 0;
  for( i = 0; i < n; i++ )
    dmax = max( dmax, dist[i] );
  fout << dmax;
  return 0;
}