Descomposició en cicles P28753


Statement
 

pdf   zip

thehtml

Donada una permutació p0, …, pn−1 dels nombres entre 0 i n−1, descomposeu-la en cicles. Interpreteu cada pi com la posició del següent element que cal visitar.

Per exemple, si la permutació és 4 2 1 5 3 0, llavors p0 = 4 ens diu que anem a la posició 4, p4 = 3 ens diu que anem a la posició 3, p3 = 5 ens diu que anem a la posició 5, i p5 = 0 ens diu que anem a la posició 0, cosa que tanca un cicle.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb un nombre n seguit d’una permutació dels nombres entre 0 i n−1. Podeu suposar 1 ≤ n ≤ 104.

Sortida

Per a cada cas, escriviu cada cicle en una línia. Escriviu els cicles ordenats en funció del seu nombre més petit, i començant en aquest nombre. Escriviu una línia amb 10 guions al final de cada cas.

Public test cases
  • Input

    6
    4 2 1 5 3 0
    3
    0 1 2
    10
    7 2 8 6 1 3 0 9 5 4
    

    Output

    0 4 3 5
    1 2
    ----------
    0
    1
    2
    ----------
    0 7 9 4 1 2 8 5 3 6
    ----------
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++