Cod sursa(job #1318009)

Utilizator hrazvanHarsan Razvan hrazvan Data 15 ianuarie 2015 15:00:00
Problema Diametrul unui arbore Scor 90
Compilator c Status done
Runda Arhiva educationala Marime 1.38 kb
#include <stdio.h>
#define MAXN 100000
int nod[2 * MAXN + 1], next[2 * MAXN + 1], ult[MAXN + 1];

inline int max2(int a, int b){
  return a > b ? a : b;
}

inline void add(int x, int y, int *k){
  nod[*k] = y;
  next[*k] = ult[x];
  ult[x] = *k;
  (*k)++;
}

int dfs(int prev, int x, int *d){
  int poz = ult[x], rez, nodf = x, df = *d, aux;
  while(poz != 0){
    if(nod[poz] != prev){
      aux = (*d) + 1;
      rez = dfs(x, nod[poz], &aux);
      if(aux > df){
        df = aux;
        nodf = rez;
      }
    }
    poz = next[poz];
  }
  *d = df;
  return nodf;
}

int bfs(int x){
  int qu[MAXN], dist[MAXN], i, st = 0, dr = 1, poz;
  char tr[MAXN];
  for(i = 0; i <= MAXN; i++)
    tr[i] = 0;
  qu[0] = x;
  dist[0] = 1;
  tr[x] = 1;
  while(st < dr){
    poz = ult[qu[st]];
    while(poz > 0){
      if(!tr[nod[poz]]){
        tr[nod[poz]] = 1;
        qu[dr] = nod[poz];
        dist[dr] = dist[st] + 1;
        dr++;
      }
      poz = next[poz];
    }
    st++;
  }
  return dist[dr - 1];
}

int main(){
  FILE *in = fopen("darb.in", "r");
  int n, i, x, y, dr = 1;
  fscanf(in, "%d", &n);
  for(i = 0; i < n; i++){
    fscanf(in, "%d%d", &x, &y);
    add(x, y, &dr);
    add(y, x, &dr);
  }
  fclose(in);
  int aux = 0;
  FILE *out = fopen("darb.out", "w");
  fprintf(out, "%d", bfs(dfs(0, 1, &aux)));
  fclose(out);
  return 0;
}