Cod sursa(job #1293951)

Utilizator andrei_r_97Radoi Andrei andrei_r_97 Data 16 decembrie 2014 20:05:30
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

const int MAX_N = 100000;

vector<int> lista[MAX_N+1];

int n, distanta, maxDistanta, maxim;
char vizitat[MAX_N+1];


void citire(FILE *in) {
  fscanf(in,"%d",&n);
  int i, a, b;
  for ( i = 1; i < n; i++ ) {
    fscanf(in,"%d %d", &a, &b);
    lista[a].push_back(b);
    lista[b].push_back(a);
  }
}

void DFS(int nod) {
  vizitat[nod] = 1;
  if ( distanta > maxDistanta ) {
    maxDistanta = distanta;
    maxim = nod;
  }
  for ( unsigned int p = 0; p < lista[nod].size(); p++ ){
    if ( !vizitat[lista[nod][p]] ) {
      distanta++;
      DFS(lista[nod][p]);
      distanta--;
    }
  }
}

int main()
{
  FILE *in  = fopen("diametru.in","r");
  FILE *out = fopen("diametru.out","w");

  citire(in);

  DFS(1);
  int i;
  for ( i = 1; i <= n; i++ )
    vizitat[i] = 0;
  DFS(maxim);


  fprintf(out,"%d",maxDistanta+1);

  fclose(in);
  fclose(out);

  return 0;
}