Cod sursa(job #3229971)

Utilizator dorin.ileailea dorin dorin.ilea Data 18 mai 2024 15:41:58
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
using namespace std;

class Task {
 public:
  void solve() {
    read_input();
    int diameter = get_diameter();
    print_output(diameter);
  }

 private:
  int n;
  vector<vector<int>> adj;

  void read_input() {
    ifstream fin("darb.in");
    fin >> n;
    adj.resize(n + 1);
    for (int i = 0; i < n - 1; ++i) {
      int a, b;
      fin >> a >> b;
      adj[a].push_back(b);
      adj[b].push_back(a);
    }
    fin.close();
  }

  pair<int, int> bfs(int start) {
    vector<int> dist(n + 1, -1);
    queue<int> q;
    q.push(start);
    dist[start] = 0;

    int farthest_node = start;
    while (!q.empty()) {
      int node = q.front();
      q.pop();

      for (int neighbor : adj[node]) {
        if (dist[neighbor] == -1) {
          dist[neighbor] = dist[node] + 1;
          q.push(neighbor);
          if (dist[neighbor] > dist[farthest_node]) {
            farthest_node = neighbor;
          }
        }
      }
    }

    return {farthest_node, dist[farthest_node]};
  }

  int get_diameter() {
    pair<int, int> first_bfs = bfs(1);
    pair<int, int> second_bfs = bfs(first_bfs.first);
    return second_bfs.second + 1;
  }

  void print_output(int diameter) {
    ofstream fout("darb.out");
    fout << diameter << endl;
    fout.close();
  }
};

int main() {
  auto* task = new (nothrow) Task();
  if (!task) {
    return -1;
  }
  task->solve();
  delete task;
  return 0;
}