Cod sursa(job #2464862)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 28 septembrie 2019 23:56:38
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_V = 100005;

int n;
int leaf, diam;

int level[MAX_V];

vector < int > G[MAX_V];

void dfs(int u) {
  for (int v : G[u]) {
    if (level[v] == 0) {
      level[v] = 1 + level[u];
      if (level[v] > diam) {
        diam = level[v];
        leaf = v;
      }
      dfs(v);
    }
  }
}

int main() {
  freopen("darb.in", "r", stdin);
  freopen("darb.out", "w", stdout);
  scanf("%d", &n);
  for (int i = 2; i <= n; ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  level[1] = 1;
  dfs(1);
  memset(level, 0, sizeof(level));
  diam = 0;
  level[leaf] = 1;
  dfs(leaf);
  printf("%d", diam);
  return 0;
}