Cicle més llarg P41101


Statement
 

pdf   zip

thehtml

Donada una permutació, quin és el seu cicle més llarg?

Per exemple, considereu la permutació (2, 6, 3, 5, 4, 1):

  • Si mirem la primera posició, ens diu que anem a la posició 2. La segona posició ens diu que anem a la posició 6. La sisena posició ens diu que tornem a la posició 1, tancant un cicle de longitud 3.
  • La tercera posició ens diu que ens quedem a la tercera posició, tancant un cicle de longitud 1.
  • Finalment, la quarta posició ens du a la cinquena, i la cinquena ens torna a la quarta, tancant un cicle de longitud 2.

Per tant, el cicle més llarg d’aquesta permutació té longitud 3.

Entrada

L’entrada consisteix en diversos casos, cadascun amb una n entre 1 i 105, seguida d’una permutació de {1, …, n}.

Sortida

Per a cada cas, escriviu la longitud del cicle més llarg.

Public test cases
  • Input

    6  2 6 3 5 4 1
    5  1 2 3 4 5
    4  3 1 4 2
    

    Output

    3
    1
    4
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++