Cod sursa(job #2042773)

Utilizator danny794Dan Danaila danny794 Data 19 octombrie 2017 06:30:12
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <vector>

std::ifstream cin("darb.in");
std::ofstream cout("darb.out");
int n, x, y;
std::vector<std::vector<int>> children;
std::vector<bool> visited;

int findParent() {
  for (int i = 1; i <= n; i++) {
    if (children[i].size() > 1) {
      return i;
    }
  }
  return -1;
}

int findDepth(int node, int depth) {
  visited[node] = true;
  int maxDepth = depth, aux = 0;
  for (const auto& child : children[node]) {
    if (!visited[child]) {
      maxDepth = std::max(maxDepth, findDepth(child, depth + 1));
    }
  }
  return maxDepth;
}

int main() {
  cin >> n;
  if (n == 2) {
    cout << 2;
    exit(0);
  }
  children.resize(n + 1);
  visited.resize(n + 1);
  for (int i = 1; i < n; i++) {
    cin >> x >> y;
    children[x].emplace_back(y);
    children[y].emplace_back(x);
  }
  int start = findParent();
  visited[start] = true;
  x = y = -1;
  for (const auto& child : children[start]) {
    int aux = findDepth(child, 1);
    if (aux >= x) {
      y = x;
      x = aux;
    } else if (aux > y) {
      y = aux;
    }
  }
  cout << x + y + 1;
  return 0;
}