Cod sursa(job #1823809)

Utilizator TincaMateiTinca Matei TincaMatei Data 6 decembrie 2016 20:59:30
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>

const int MAX_N = 100000;

int mc[1+2*MAX_N], next[1+2*MAX_N], last[1+MAX_N];

inline void addMuchie(int a, int b, int id) {
  mc[id] = b;
  next[id] = last[a];
  last[a] = id;
}

int max, nodeMax;

void dfs(int node, int papa, int nodes) {
  int i;
  if(nodes > max) {
    max = nodes;
    nodeMax = node;
  }
  i = last[node];
  while(i != 0) {
    if(mc[i] != papa)
      dfs(mc[i], node, nodes + 1);
    i = next[i];
  }
}

int main() {
  int n, a, b;
  FILE *fin = fopen("darb.in", "r");
  fscanf(fin, "%d", &n);
  for(int i = 0; i < n - 1; ++i) {
    fscanf(fin, "%d%d", &a, &b);
    addMuchie(a, b, i * 2 + 1);
    addMuchie(b, a, i * 2 + 2);
  }
  fclose(fin);

  dfs(1, 0, 1);
  max = 0;
  dfs(nodeMax, 0, 1);

  FILE *fout = fopen("darb.out", "w");
  fprintf(fout, "%d", max);
  fclose(fout);
  return 0;
}