Cod sursa(job #2922643)

Utilizator raresgherasaRares Gherasa raresgherasa Data 9 septembrie 2022 14:31:57
Problema Diametrul unui arbore Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NM = 1e5 + 5;

int d[NM], n;
set<int>g[NM];

int main(){
  ios_base::sync_with_stdio(false);
  fin >> n;
  for (int i = 0; i < n - 1; i++){
    int x, y; fin >> x >> y;
    g[x].insert(y);
    g[y].insert(x);
  }
  queue<int>q;
  d[1] = 1;
  q.push(1);
  while (!q.empty()){
    int k = q.front();
    q.pop();
    for (int u : g[k]){
      if (d[u] == 0){
        d[u] = d[k] + 1;
        q.push(u);
      }
    }
  }
  int mx = 0, e = 1;
  for (int i = 1; i <= n; i++){
    if (d[i] > mx){
      mx = d[i];
      e = i;
    }
  }
  memset(d, 0, sizeof(d));
  d[e] = 1;
  q.push(e);
  while (!q.empty()){
    int k = q.front();
    q.pop();
    for (int u : g[k]){
      if (d[u] == 0){
        d[u] = d[k] + 1;
        q.push(u);
      }
    }
  }
  fout << *max_element(d + 1, d + n + 1);
}