Cod sursa(job #1541889)

Utilizator andrei_diaconu11Andrei C. Diaconu andrei_diaconu11 Data 4 decembrie 2015 17:42:59
Problema Diametrul unui arbore Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.84 kb

#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100000
int vf[2*MAX_N+1], lst[MAX_N+1], next[2*MAX_N+1], m=0, q[MAX_N+1], d[MAX_N+1], n;
char f[MAX_N+1];

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

void bfs(int a){
  int st=1, dr=1, i, x;
  q[dr]=a;
  for(i=1;i<=n;i++)
    f[i]=0;
  f[a]=1;
  d[a]=0;
  while(st<=dr){
    x=lst[q[st]];
    while(x!=0){
      if(f[vf[x]]==0){
        f[vf[x]]=1;
        dr++;
        q[dr]=vf[x];
        d[vf[x]]=d[q[st]]+1;
      }
      x=next[x];
    }
    st++;
  }
}

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