Convención P75322


Statement
 

pdf   zip

thehtml

Este año, Walker no podrá asistir a la convención nacional de rangers. Por eso le pide a Trivette que vaya en su lugar. Cuando Trivette llega al lugar se da cuenta de que no conoce a nadie. Como que a él le gustaría conocer a los presentes, va a tener que presentarse a todos ellos, uno por uno. Por ejemplo, para conocer a “Roger”, puede ir y decirle “Hola Roger, permíteme que me presente, soy Trivette.”. Pero presentarse directamente a un desconocido resulta un poco embarazoso. Por ello, una vez conoce a una persona, puede pedirle a ésta que le presente a sus conocidos, lo cual resulta más fácil. Por ejemplo, si “Roger” conoce a “Sullivan”, puede decirle a “Roger” lo siguiente: “Roger, podrías presentarme a Sullivan?”. Si luego “Sullivan” conoce a “Jack”, podrá pedirle “Sullivan, podrías presentarme a Jack?”. Con ello, Trivette habría conocido a tres personas usado una única auto- presentación.

Debes escribir un programa que, dada la lista de personas presentes, y la relación de conocimiento mútuo entre ellas, sea capaz de calcular el mínimo número de auto-presentaciones que necesitará Trivette para acabar conociendo a todo el mundo.

Entrada

La entrada tiene, en una primera línea, un número entero n que cumple 1≤ n≤ 105, que representa el número total de personas. Después vienen n líneas, con un nombre en cada una de ellas, que representa el conjunto de personas presentes, y donde cada nombre se constituye de como mucho 10 letras mayúsculas y minúsculas. En una nueva línea hay un número entero m que cumple 1≤ m≤ 50000, que representa el número de relaciones de conocimiento mútuo. Después vienen m líneas, con dos nombres X e Y en una línea, para indicar que X e Y se conocen. La pareja X Y únicamente aparece una vez en la entrada (bien sea X Y, o bien Y X). Nunca aparecerán auto-relaciones de amistad (X X).

Salida

Escribe una línea con el mínimo número de auto-presentaciones que necesitará Trivette para acabar conociendo a todas las personas.

Puntuación

  • TestA:  ‍ Entradas con NUM que cumplan 1≤ n,m≤ 4.  ‍25 Puntos ‍
  • TestB:  ‍ Entradas con NUM que cumplan 1≤ n,m≤ 100.  ‍25 Puntos ‍
  • TestC:  ‍ Entradas con NUM que cumplan 1≤ n,m≤ 2000.  ‍25 Puntos ‍
  • TestD:  ‍ Entradas con NUM que cumplan 1≤ n,m≤ 50000.  ‍25 Puntos ‍
Public test cases
  • Input

    2
    Roger
    Sullivan
    1
    Roger Sullivan
    

    Output

    1
    
  • Input

    4
    Carlos
    Antonio
    Borja
    Daniel
    2
    Daniel Borja
    Antonio Daniel
    

    Output

    2
    
  • Input

    10
    Jack
    Donovan
    Rudy
    Arthur
    Sonia
    Debra
    Dexter
    Mortadelo
    Filemon
    Bacterio
    6
    Jack Donovan
    Jack Rudy
    Debra Dexter
    Mortadelo Filemon
    Filemon Bacterio
    Bacterio Mortadelo
    

    Output

    5
    
  • Information
    Author
    Guillem Godoy
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++