Cod sursa(job #2290781)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 26 noiembrie 2018 23:04:15
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

FILE *fin = fopen ("darb.in", "r"), *fout = fopen ("darb.out", "w");

const int MAXN = 1e5;

vector <int> gr[MAXN + 1];

int depth[MAXN + 1];
int mx, maxleaf;
void dfs (int nod, int tata) {
  for (auto fiu : gr[nod]) {
    if (fiu != tata) {
      depth[fiu] = depth[nod] + 1;
      if (depth[fiu] > mx) {
        mx = depth[fiu];
        maxleaf = fiu;
      }
      dfs (fiu, nod);

    }
  }
}

int main() {
  int n, i, x, y;
  fscanf (fin, "%d", &n);
  for (i = 2; i <= n; i++) {
    fscanf (fin, "%d%d", &x, &y);
    gr[x].push_back (y);
    gr[y].push_back (x);
  }
  mx = 0;
  maxleaf = 1;
  dfs (1, -1);
  memset (depth, 0, sizeof (depth));
  mx = 0;
  dfs (maxleaf, -1);
  fprintf (fout, "%d", mx + 1);
  fclose (fin);
  fclose (fout);
  return 0;
}