fork download
copy 
  1. program espias_100;
  2.  
  3. var
  4.    n, i, j, k, espiaActual, apuntadorPila, largociclo, maximo : integer;
  5.    esCiclo : boolean;
  6.    espias : array [1..1000000] of integer;
  7.    leidos : array [1..1000000] of integer;
  8.    leidosDesdeEspia : array [1..1000000] of integer;
  9.    pila : array [1..1000001] of  integer;
  10.  
  11. begin
  12.      readln(n);
  13.      for i:=1 to n do begin
  14.          readln(espias[i]);
  15.          leidos[i]:=0;
  16.          leidosDesdeEspia[i]:=0;
  17.      end;
  18.  
  19.      maximo:=0;
  20.      apuntadorPila:=1;
  21.      j:=1; // VAMOS A UTILIZAR j PARA IR NUMERANDO LOS CICLOS Y NO CONFUNDIRNOS ENTRE EL CICLO QUE ESTAMOS BUSCANDO Y ANTERIORES
  22.      // OBTEN LOS MAXIMOS EMPEZANDO DESDE TODOS LOS ESPIAS
  23.      for i:=1 to n do begin
  24.          if leidos[i] = 0 then begin // NO SE HA PASADO POR ESTE ESPIA NUNCA
  25.             espiaActual:=i;
  26.             while leidos[espiaActual] = 0 do begin // RECORRE DESDE ESTE ESPIA HASTA ENCONRAR SU CICLO O CHOCAR CON UN CICLO ENCONTRADO PREVIAMENTE
  27.                   leidos[espiaActual]:=j;
  28.                   pila[apuntadorPila]:=espiaActual;
  29.                   Inc(apuntadorPila);
  30.                   espiaActual:=espias[espiaActual];
  31.             end;
  32.  
  33.             if leidos[espiaActual] = j then begin // ENCONTRAMOS UN CICLO, HAY QUE MEDIR LA LONGITUD
  34.                largoCiclo:=0;
  35.                for k:=apuntadorPila - 1 downto 1 do begin // BUSCA EL LARGO DEL CICLO
  36.                    if pila[k] = espiaActual then
  37.                       break
  38.                    else
  39.                        Inc(largoCiclo);
  40.                end;
  41.                // ACTUALIZA LOS MAXIMOS, TODOS LOS ELEMENTOS DEL CICLO DEBEN TENER EL MISMO VALOR
  42.                esCiclo:=true;
  43.                while apuntadorPila > 1 do begin
  44.                      Dec(apuntadorPila);
  45.                      if esCiclo then
  46.                         leidosDesdeEspia[pila[apuntadorPila]]:=largoCiclo
  47.                      else
  48.                          leidosDesdeEspia[pila[apuntadorPila]]:=leidosDesdeEspia[espias[pila[apuntadorPila]]] + 1;
  49.  
  50.                      if pila[apuntadorPila] = espiaActual then esCiclo:=false;
  51.                end;
  52.             end
  53.             else begin // SOMOS UNA RAMA, LLEGAMOS A UN CICLO O RAMA PREVIA, HAY QUE ACTUALIZAR LAS LONGITUDES
  54.                  while apuntadorPila > 1 do begin
  55.                        Dec(apuntadorPila);
  56.                        leidosDesdeEspia[pila[apuntadorPila]]:=leidosDesdeEspia[espias[pila[apuntadorPila]]] + 1;
  57.                  end;
  58.             end;
  59.          end;
  60.          Inc(j);
  61.      end;
  62.  
  63.      // BUSCA EL MAXIMO
  64.      for i:=1 to n do
  65.          if leidosDesdeEspia[i] > maximo then
  66.             maximo:=leidosDesdeEspia[i];
  67.  
  68.      write(maximo);
  69. end.
  70.  
Success #stdin #stdout 0s 5392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/siMHsA
language:
Pascal (fpc 3.0.4)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!