Cod sursa(job #1293955)

Utilizator andrei_r_97Radoi Andrei andrei_r_97 Data 16 decembrie 2014 20:06:42
Problema Diametrul unui arbore Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.08 kb
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100000

typedef struct lista {
  int nod;
  struct lista *next;
} lista;

lista *g[MAX_N+1];

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

void adaugare(int i, int j) {
  lista *p = malloc(sizeof(lista));
  p -> nod = j;
  p -> next = g[i];
  g[i] = p;
}

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

void DFS(int nod) {
  vizitat[nod] = 1;
  if ( distanta > maxDistanta ) {
    maxDistanta = distanta;
    max = nod;
  }
  lista *p;
  for ( p = g[nod]; p != NULL; p = p -> next ){
    if ( !vizitat[p -> nod] ) {
      distanta++;
      DFS(p -> nod);
      distanta--;
    }
  }
}

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

  citire(in);

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


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

  fclose(in);
  fclose(out);

  return 0;
}