Cod sursa(job #2885150)

Utilizator avtobusAvtobus avtobus Data 5 aprilie 2022 16:03:00
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

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


int main(void) {
  // freopen("darb.in", "r", stdin);
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int N;
  fin >> N;
  vector<vector<int>> tree(N);
  for(int i = 0; i < N-1; i++) {
    int u,v;
    fin >> u >> v;
    --u, --v;
    tree[u].push_back(v);
    tree[v].push_back(u);
  }
  vector<int> d(N, -1);
  auto bfs = [&](int origin)->int {
    int end_node = origin, max_dist = 0;
    fill(d.begin(), d.end(), -1);
    d[origin] = 0;
    queue<int> q;
    q.push(origin);
    while(!q.empty()) {
      int nod = q.front(); q.pop();
      if (d[nod] > max_dist) {
        end_node = nod;
        max_dist = d[nod];
      }
      for(auto nbr: tree[nod]) {
        if (d[nbr] != -1) continue;
        d[nbr] = d[nod] + 1;
        q.push(nbr);
      }
    }

    return end_node;
  };

  int a = bfs(0);
  int b = bfs(a);

  fout << d[b] + 1 << "\n";

  return 0;
}