Experiencia de entrevista de National Instruments | conjunto 2

Comercio interplanetario:
Hober Mallow quiere establecer un comercio intergaláctico que permita el comercio entre diferentes planetas. Cada planeta tiene su propio conjunto de monedas en las que comercian. Como hay demasiadas monedas, Hober decidió declarar un conjunto de monedas M (numeradas del 1 al M) como las monedas oficiales que se pueden usar para comerciar entre planetas. Dos planetas pueden comerciar si y solo si tienen una moneda oficial común o si hay otro planeta con el que cada uno de estos planetas comparte una moneda oficial común. Por ejemplo, digamos que el planeta A tiene monedas: 1, 3, 4, el planeta B tiene monedas 5, 6 y el planeta C tiene 6, 4. Todavía es posible que el planeta A y B intercambien a través del planeta C (planeta A -> C a través de la moneda 4 y luego el planeta C ->B a través de la moneda 6 y viceversa). Este tipo de comercio se puede realizar con más de un planeta actuando también como intermediario (es decir, el planeta X e Y pueden comerciar a través de A, B, C si XA comparte una moneda común, AB comparte una moneda común, BC comparte una moneda común y finalmente CY comparte una moneda común). Hober observa que, incluso con estas reglas, hay planetas que no tienen monedas oficiales o grupos de planetas que no comparten ninguna moneda con otros grupos de planetas. Para permitir el comercio entre todos los planetas, tiene que implementar un sistema de nueva moneda para cada uno de esos planetas que no tienen monedas oficiales u oficiales comunes. Implementar un nuevo sistema monetario le cuesta 1 unidad de platino por planeta. Tienes que ayudar a Hober a minimizar el costo de permitir el comercio entre todos los planetas. BC comparte una moneda común y finalmente CY comparte una moneda común). Hober observa que, incluso con estas reglas, hay planetas que no tienen monedas oficiales o grupos de planetas que no comparten ninguna moneda con otros grupos de planetas. Para permitir el comercio entre todos los planetas, tiene que implementar un sistema de nueva moneda para cada uno de esos planetas que no tienen monedas oficiales u oficiales comunes. Implementar un nuevo sistema monetario le cuesta 1 unidad de platino por planeta. Tienes que ayudar a Hober a minimizar el costo de permitir el comercio entre todos los planetas. BC comparte una moneda común y finalmente CY comparte una moneda común). Hober observa que, incluso con estas reglas, hay planetas que no tienen monedas oficiales o grupos de planetas que no comparten ninguna moneda con otros grupos de planetas. Para permitir el comercio entre todos los planetas, tiene que implementar un sistema de nueva moneda para cada uno de esos planetas que no tienen monedas oficiales u oficiales comunes. Implementar un nuevo sistema monetario le cuesta 1 unidad de platino por planeta. Tienes que ayudar a Hober a minimizar el costo de permitir el comercio entre todos los planetas. Para permitir el comercio entre todos los planetas, tiene que implementar un sistema de nueva moneda para cada uno de esos planetas que no tienen monedas oficiales u oficiales comunes. Implementar un nuevo sistema monetario le cuesta 1 unidad de platino por planeta. Tienes que ayudar a Hober a minimizar el costo de permitir el comercio entre todos los planetas. Para permitir el comercio entre todos los planetas, tiene que implementar un sistema de nueva moneda para cada uno de esos planetas que no tienen monedas oficiales u oficiales comunes. Implementar un nuevo sistema monetario le cuesta 1 unidad de platino por planeta. Tienes que ayudar a Hober a minimizar el costo de permitir el comercio entre todos los planetas.

Se le dará N (2 <= N <= 50) que indica el número de planetas que quieren ser parte del comercio intergaláctico. Se le dará M (2 <= M <= 50) que indica el número de moneda oficial numerada del 1 al M. A esto le seguirán N líneas, cada una compuesta por un número Ci, el número de monedas oficiales admitidas por el planeta i , seguido de las monedas C que se intercambian por el i-ésimo planeta. Debe generar la cantidad de unidades de platino requeridas para permitir el comercio en todos los planetas.

Entradas de ejemplo

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

5 5
0
3 4 1 5
2 3 4
0
1 2
Productos esperados

0
Los planetas n.° 1 y n.° 2 pueden operar con la moneda 2. Los planetas n.° 2 y n.° 3 pueden operar con la moneda 3. Los planetas n.° 3 y n.° 4 pueden operar con la moneda 4. Los planetas n.° 4 y n.° 5 pueden operar con la moneda 5. Es posible comerciar entre dos planetas cualquiera a través de cero o más planetas intermediarios. Por lo tanto, no hay necesidad de configurar una nueva moneda y, por lo tanto, el costo es 0.
3
Los planetas n.° 2 y n.° 3 pueden comerciar a través de la moneda 4, pero los planetas n.° 1, n.° 4 y n.° 5 no comparten ninguna moneda entre sí o con #2 y #3 y por lo tanto no puede comerciar con nadie más. Una de las monedas de los planetas #2 o #3 se puede configurar en los planetas #1, #4 y #5, lo que haría posible el comercio entre todos los planetas. Como la moneda deberá configurarse en 3 planetas diferentes, el costo es 3.

Entradas y salidas
de ejemplo Caso de prueba Entrada Salida Enlace de descarga Ejecutar enlace (también guarda el código)
1
5 5
1 2
2 2 3
2 3 4
2 4 5
1 5
0
Descargar archivo de entrada Ejecutar contra código
2
5 5
0
3 4 1 5
2 3 4
0
1 2
3
Descargar archivo de entrada Ejecutar contra código
Límite de tiempo por caso de prueba:

2 segundos)

Si tiene una máquina con GCC/G++ y desea trabajar sin conexión, descargue la plantilla aquí y envíela

Plantillas de código:

Plantilla C: Trade.c

Plantilla C++: Comercio.cpp

Este artículo es una contribución de Bharat. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo electrónico a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.