Cod sursa(job #2342154)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 12 februarie 2019 17:05:40
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

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

const int NMAX = 100005;

int N;
vector <int> Ad[NMAX];

int dist_max;

int BFS( int nod )
{
  int dist[NMAX] = { 0 };
  int w, u;

  deque <int> Q;

  dist[nod] = 1;
  Q.push_back( nod );

  while( !Q.empty() )
  {
    u = Q.front();
    Q.pop_front();

    for( int i = 0; i < Ad[u].size(); ++i )
    {
      w = Ad[u][i];

      if( dist[w] == 0 )
      {
        dist[w] = dist[u] + 1;
        Q.push_back( w );
      }
    }
  }

  int d_max = 0, n_max;

  for( int i = 1; i <= N; ++i )
    if( dist[i] > d_max )
    {
      d_max = dist[i];
      n_max = i;
    }

  dist_max = d_max;

  return n_max;
}

int main()
{
    fin >> N;

    int x, y;
    for( int i = 1; i < N; ++i )
    {
      fin >> x >> y;

      Ad[x].push_back(y);
      Ad[y].push_back(x);
    }

    int endpoint = BFS( 1 );

    BFS( endpoint );

    fout << dist_max << '\n';


    return 0;
}