Cod sursa(job #2883515)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 1 aprilie 2022 16:11:21
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

vector<int> gr[N];
int d1[N], d2[N];

void dfs(int nod, int d[]) {
  for (auto vec: gr[nod])
   if (d[vec] == 0) {
      d[vec] = d[nod] + 1;
      dfs(vec, d);
   }
}

int main() {
  ifstream cin("darb.in");
  ofstream cout("darb.out");
  int n;
  cin >> n;
  for (int i = 0; i < n - 1; ++i) {
    int x, y;
    cin >> x >> y;
    gr[x].push_back(y);
    gr[y].push_back(x);
  }
  cin.close();
  d1[1] = 1;
  dfs(1, d1);
  int cap, maxi = 0;
  for (int i = 1; i <= n; ++i)
    if (d1[i] > maxi) {
      maxi = d1[i];
      cap = i;
    }
  d2[cap] = 1;
  dfs(cap, d2);
  int ans = 0;
  for (int i = 1; i <= n; ++i)
    ans = max(ans, d2[i]);
  cout << ans << "\n";
  cout.close();
  return 0;
}