Amistat a la xarxa P11840


Statement
 

pdf   zip

html

Una nova xarxa social s’ha posat de moda, i n persones s’hi han apuntat. Inicialment, ningú coneix a ningú. Després, de tant en tant dues persones es fan amigues (directes). Feu un programa que mantingui el nombre d’amics de cadascú a cada moment, suposant que la relació d’amistat és d’equivalència. En particular, suposeu que els amics dels amics també són (transitivament) amics.

Entrada

L’entrada consisteix en diversos casos, cadascun amb el nombre de persones n i la quantitat d’operacions q. Segueixen les q operacions, de dos tipus:

  • c x: Consulta el nombre d’amics de x (x inclòs).
  • a x y: Indica que x i y, amb xy, s’han fet amics directes. No fa res si x i y ja eren amics, ja sigui directament o indirectament.

Suposeu 2 ≤ n ≤ 104, nq ≤ 5n, i que les persones es numeren entre 1 i n.

Sortida

Per a cada cas, i per a cada operació de consulta, escriviu el nombre d’amics de la persona consultada. Escriviu una línia amb 10 guions al final de cada cas.

Public test cases
  • Input

    2 2
    a 2 1
    c 2
    
    4 11
    c 1
    c 2
    a 1 2
    c 1
    c 2
    c 4
    a 4 1
    c 2
    a 2 4
    c 2
    c 3
    

    Output

    2
    ----------
    1
    1
    2
    2
    1
    3
    3
    1
    ----------
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python