Cod sursa(job #2885147)

Utilizator avtobusAvtobus avtobus Data 5 aprilie 2022 15:57:35
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 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);
  }
  auto bfs = [&](int origin)->pair<int,int> {
    int end_node = origin, max_dist = 0;
    vector<int> d(N, -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, max_dist};
  };

  int a = bfs(0).first;
  int dist = bfs(a).second;

  fout << dist + 1 << "\n";

  return 0;
}