Cod sursa(job #2611543)

Utilizator RobertLicaRobert Lica RobertLica Data 7 mai 2020 00:44:04
Problema Diametrul unui arbore Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>

#define FILE_I "darb.in"
#define FILE_O "darb.out"
#define ROOT 1

using namespace std;

class Task {
  int n;
  std::vector< std::vector< int>> adj;
  std::vector<int> t_out;
  int solutie = 0;


 public:
  void solve() {
    read();
    fa();
    print();
  }

 private:
  void read() {
    std::ifstream fin(FILE_I);
    fin >> n;
    adj.resize(n + 1);

    int x, y;
    for (int i = 0; i < n - 1; ++i) {
      fin >> x >> y;
      adj[x].push_back(y);
    }
    fin.close();
  }

  void fa() {
    std::vector<int> vizitat(n + 1, 0);

    int i = ROOT;
    vizitat[i] = 0;
    for (auto &x : adj[i]) {
      vizitat[x] = vizitat[i] + 1;
      dfs(x, vizitat);
    }

    compute_solution(vizitat);
  }

  void dfs(int nod, vector<int> &vizitat) {
    for (auto &x : adj[nod]) {
      vizitat[x] = vizitat[nod] + 1;
      dfs(x, vizitat);
    }
  }

  void compute_solution(vector<int> &vizitat) {
    int x = 0, y = 0;
    for (unsigned int i = 1; i < vizitat.size(); ++i) {
      if (vizitat[i] > y) {
        x = y; 
        y = vizitat[i];
      }
    }
    solutie = x + y + 1;
  }

  void print() {
    std::ofstream fout (FILE_O);
    fout << solutie;
    fout.close();
  }
};

int main() {
  Task *t = new Task();
  t->solve();
  delete t;
  return 0;
}