Cod sursa(job #2708837)

Utilizator vladbalteanuVlad Balteanu vladbalteanu Data 19 februarie 2021 15:05:10
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream cin("darb.in");
ofstream cout("darb.out");

vector <int> lista[100001];
int viz[100001],coada[100001],n;
int l[100001];

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, f;
  cin >> n;
  for(i=1;i<=n-1;i++){
    cin >> n1 >> n2;
    lista[n1].push_back(n2);
    lista[n2].push_back(n1);
  }
  bfs(1);
  maxim=0;
  f=1;
  for(i=1;i<=n;i++)
  {
    if(l[i]>maxim)
    {
      maxim=l[i];
      f=i;
    }
    viz[i]=l[i]=0;
  }
  bfs(f);
  maxim=0;
  for(i=1;i<=n;i++)
    if(l[i]>maxim)
      maxim=l[i];
  cout<<maxim;
  return 0;
}