table.pas

   1 var
   2         a,b,group:array [0..500,0..500] of longint;
   3         f:array [0..500] of boolean;
   4         g:array [0..500,0..2] of longint;
   5         n,i,j,k,j1,t,t1,numofgroup,p,q,ans:longint;
   6
   7 function min(a,b:longint):longint;
   8 begin
   9         if a<b then exit(a) else exit(b);
  10 end;
  11
  12 function max(a,b:longint):longint;
  13 begin
  14         if a>b then exit(a) else exit(b);
  15 end;
  16
  17 procedure floyd;
  18 var
  19         i,j,k:longint;
  20
  21 begin
  22         for k:=1 to n do
  23                 for i:=1 to n do
  24                         for j:=1 to n do
  25                                 b[i,j]:=min(b[i,j],b[i,k]+b[k,j]);
  26 end;
  27
  28 procedure floodfill(k,num,sum:longint);
  29 var
  30         i:longint;
  31
  32 begin
  33         f[k]:=true; inc(group[num,0]); group[num,sum]:=k;
  34         for i:=1 to n do
  35                 if (i<>k) and (f[i]=false) and (a[k,i]=1) then
  36                         begin
  37                                 floodfill(i,num,sum+1);
  38                         end;
  39 end;
  40
  41 procedure sort;
  42 var
  43         i,j:longint;
  44
  45 begin
  46         for i:=1 to numofgroup-1 do
  47                 for j:=i+1 to numofgroup do
  48                         if g[i,1]>g[j,1] then
  49                                 begin
  50                                         g[0]:=g[i]; g[i]:=g[j]; g[j]:=g[0];
  51                     group[0]:=group[i]; group[i]:=group[j]; group[j]:=group[0];
  52                                 end;
  53 end;
  54
  55 procedure insertsort(k:longint);
  56 var
  57         i,j:longint;
  58
  59 begin
  60         g[0]:=g[k];
  61         g[k,1]:=0;
  62         j:=k;
  63         while (g[j,1]<g[0,1]) and (j<numofgroup) do inc(j);
  64         for i:=1 to j-2 do g[i]:=g[i+1];
  65         g[j-1]:=g[0];
  66 end;
  67
  68 begin
  69         readln(n);
  70         readln(p,q);
  71         while (p<>0) and (q<>0) do
  72                 begin
  73                         a[p,q]:=1;
  74                         a[q,p]:=1;
  75                         readln(p,q);
  76                 end;
  77         b:=a;
  78         for i:=1 to n do
  79                 for j:=1 to n do
  80                         if b[i,j]=0 then b[i,j]:=maxint;
  81         for i:=1 to n do b[i,i]:=0;
  82         floyd;
  83         for i:=1 to n do
  84                 if f[i]=false then
  85                         begin
  86                                 inc(numofgroup);
  87                                 floodfill(i,numofgroup,1);
  88                         end;
  89         for i:=1 to numofgroup do
  90                 begin
  91                         t1:=maxint; j1:=group[i,1];
  92                         for j:=1 to group[i,0] do
  93                                 begin
  94                                         t:=0;
  95                                         for k:=1 to group[i,0] do
  96                                                 t:=max(b[group[i,j],group[i,k]],t);
  97                                         if t<t1 then begin t1:=t; j1:=j; end;
  98                                 end;
  99                         g[i,1]:=t1; g[i,2]:=group[i,j1];
 100                 end;
 101         sort;
 102         for i:=2 to numofgroup do
 103                 begin
 104                         writeln(g[i-1,2],' ',g[i,2],' ',n+i-1);
 105                         g[i,1]:=max(g[i,1],g[i-1,1])+1; g[i,2]:=n+i-1;
 106             if i<>numofgroup then insertsort(i);
 107                 end;
 108     writeln(g[numofgroup,1]);
 109 end.