Cod sursa(job #2275753)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 3 noiembrie 2018 15:26:05
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>

#define MAXN 100000

using namespace std;

vector<int> p[MAXN+5];
queue<int> q;
int lg[MAXN+5], viz[MAXN+5], l, d;

void bfs( int plecare )
{
  q.push(plecare);
  lg[plecare]=1;
  viz[plecare]=1;

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

    for( int i=0;i<p[k].size();i++ )
      if( !viz[p[k][i]] )
      {
        q.push(p[k][i]);
        lg[p[k][i]]=lg[k]+1;
        viz[p[k][i]]=1;

        d=lg[p[k][i]];
        l=p[k][i];
      }

    q.pop();
  }
}

int main()
{
  freopen( "darb.in", "r", stdin );
  freopen( "darb.out", "w", stdout );

  int n, a, b;

  scanf( "%d", &n );

  for( int i=1;i<=n;i++ )
  {
    scanf( "%d%d", &a, &b );

    p[a].push_back(b);
    p[b].push_back(a);
  }

  bfs(1);

  memset(lg,0,sizeof(lg));
  memset(viz,0,sizeof(viz));

  bfs(l);

  printf( "%d", d );

  return 0;
}