Cod sursa(job #1541623)

Utilizator cella.florescuCella Florescu cella.florescu Data 4 decembrie 2015 14:23:34
Problema Diametrul unui arbore Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100000

int vf[2*MAXN+1], lst[MAXN+1], next[2*MAXN+1], m, dist[MAXN+1], last;

void add(int x, int y){
  vf[++m]=y;
  next[m]=lst[x];
  lst[x]=m;
}

void bfs(int nod){
  int b, e, queue[MAXN+1], p;
  b=0; e=1; queue[0]=nod; dist[nod]=1;
  while(b!=e){
    last=queue[b];
    p=lst[queue[b]];
    while(p){
      if(dist[vf[p]]==0){
        dist[vf[p]]=dist[queue[b]]+1;
        queue[e++]=vf[p];
      }
      p=next[p];
    }
    ++b;
  }
}

int main()
{
    FILE *fin, *fout;
    int n, i, u, v;
    fin=fopen("darb.in", "r");
    fscanf(fin, "%d", &n);
    for(i=1; i<n; i++){
      fscanf(fin, "%d%d", &u, &v);
      add(u, v); add(v, u);
    }
    fclose(fin);
    bfs(1);
    for(i=1; i<=n; i++)
      dist[i]=0;
    bfs(last);
    fout=fopen("darb.out", "w");
    fprintf(fout, "%d\n", dist[last]);
    fclose(fout);
    return 0;
}