Amigos P49894


Statement
 

pdf   zip

thehtml

Suponed que la relación de amistad entre personas es de equivalencia, es decir:

  • Toda persona es amiga de sí misma.
  • Si x es amigo de y, entonces y es amigo de x.
  • Si x es amigo de y, e y es amigo de z, entonces x es amigo de z.

Se os dan los nombres de n personas y m relaciones (directas) de amistad. Tenéis que encontrar el menor y el mayor grupo de amigos.

Entrada

La entrada consiste en diversos casos. Cada caso empieza con un natural n ≥ 1, seguido de n nombres (palabras no vacías con letras minúsculas y mayúsculas) diferentes de personas. A continuación viene un natural m entre 0 y n(n−1)/2, seguido de m relaciones directas de amistad. En la entrada nuncá habrá relaciones de amistad repetidas, ni del tipo “x es amigo de x”. Si la entrada contiene la relación “x es amigo de y”, entonces no contendrá la relación “y es amigo de x”.

Salida

Para cada caso de la entrada, tenéis que escribir el número de caso, seguido del tamaño del grupo de amigos más pequeño, seguido del tamaño del grupo de amigos más grande.

Puntuación

  • TestA:  ‍ Prueba como los del ejemplo 1, donde n es como mucho 5.  ‍30 Puntos ‍
  • TestB:  ‍ Prueba donde n puede ser hasta 1000.  ‍50 Puntos ‍
  • TestC:  ‍ Prueba donde n puede ser hasta 5000.  ‍20 Puntos ‍
Public test cases
  • Input

    1
    Juan
    0
    
    5
    Benito
    Eduardo
    Carlos
    Ana
    Diana
    3
    Benito Eduardo
    Carlos Ana
    Diana Eduardo
    
    3
    Melchor
    Gaspar
    Baltasar
    3
    Melchor Gaspar
    Baltasar Gaspar
    Melchor Baltasar
    

    Output

    Caso #1
    minimo grupo de amigos: 1
    maximo grupo de amigos: 1
    Caso #2
    minimo grupo de amigos: 2
    maximo grupo de amigos: 3
    Caso #3
    minimo grupo de amigos: 3
    maximo grupo de amigos: 3
    
  • Input

    12
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    14
    A F
    H I
    K B
    J H
    C E
    A B
    I L
    L H
    K A
    D G
    F B
    J I
    G I
    H G
    

    Output

    Caso #1
    minimo grupo de amigos: 2
    maximo grupo de amigos: 6
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++