Cod sursa(job #2039941)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 15 octombrie 2017 10:42:32
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin("darb.in");
ofstream cout("darb.out");

void dfs(int cur_node, int cur_dist, vector < vector < int > > &gr,
  vector < bool > &used, pair < int, int > &best) {

  if (best.first < cur_dist) {
    best = {cur_dist, cur_node};
  }

  used[cur_node] = true;
  for (auto next_node : gr[cur_node]) {
    if (used[next_node]) {
      continue;
    }

    dfs(next_node, cur_dist + 1, gr, used, best);
  }
  used[cur_node] = false;
}

int main(int argc, char const *argv[]) {
  
  int n;
  cin >> n;

  vector < vector < int > > gr(n + 1);
  for (int i = 1; i < n; i ++) {
    int x, y;
    cin >> x >> y;
    gr[x].push_back(y);
    gr[y].push_back(x);
  }

  pair < int, int > best(0, 0);
  vector < bool > used(n + 1);
  dfs(1, 1, gr, used, best);
  int sol = best.second;
  best = {0, 0};
  dfs(sol, 1, gr, used, best);

  cout << best.first << '\n';
}