Cod sursa(job #1410094)

Utilizator casianos1996Marc Casian Nicolae casianos1996 Data 30 martie 2015 20:57:24
Problema Diametrul unui arbore Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.28 kb
program diametrul_unui_arbore;
var     f,g:text;
        bufin,bufout:array[1..1 shl 16] of byte;
        a:array of array of longint;
        d,viz,c,cd:array[1..100000] of longint;
        n,m,i,j,k,ultim,diametru:longint;

procedure readdata;
var       i,x,y:longint;
begin
  assign(f,'darb.in'); reset(f);
  assign(g,'darb.out'); rewrite(g);
  settextbuf(f,bufin); settextbuf(g,bufout);
  readln(f,n);
  setlength(a,n+1,1);
//  setlength(c,n+1);
  for i:=1 to n do
    begin
      readln(f,x,y);
      inc(c[x]); inc(c[y]);
      setlength(a[x],c[x]+1);
      setlength(a[y],c[y]+1);
      a[x,c[x]]:=y;
      a[y,c[y]]:=x;
    end;
  close(f);
end;

procedure bfs(nod,mark:longint);
var       i,z,st,sf:longint;
begin
  //setlength(cd,n+1);
//  setlength(viz,n+1);
  d[nod]:=0;
  st:=0; sf:=1; cd[1]:=nod; viz[nod]:=mark;
  while st<sf do
    begin
      inc(st);
      z:=cd[st];
      for i:=1 to c[z] do
        if viz[a[z,i]]<>mark then
          begin
            inc(sf);
            cd[sf]:=a[z,i];
            d[cd[sf]]:=d[cd[st]]+1;
            viz[a[z,i]]:=mark;
            diametru:=d[cd[sf]];
            ultim:=a[z,i];
          end;
    end;
end;

begin
  readdata;
  bfs(1,1);
  bfs(ultim,2);
  writeln(g,diametru+1);
  close(g);
end.