Programacion, ACM ICPC, UVa Online Judge

El link del problema es el siguiente:
924 – Spreading the News

El problema es de Grafos y se soluciona con un BFS.
El problema dice que hay una nueva noticia y cada día se esparce a los conocidos de la persona que lo conoce.
Lo que nos pide son 2 cosas:

  • El numero de personas máximo que se entera en 1 día de la noticia
  • El primer día en el que ese máximo se dio

El máximo de personas conocidas se puede dar en mas de un día, así que nos piden el primero de todos ellos.
Lo que hay que hacer es realizar un BFS y contar a cuantos nodos visitamos, pero por nivel.
Como la búsqueda en amplitud visita por niveles, solo es necesario contar que nivel tiene mas nodos y guardar que nivel fue.
Ejemplo:
6
2 1 2
2 3 4
3 0 4 5
1 4
0
2 0 2
3
0
4
5

Lo que nos dice la entrada es primero el numero de personas en la red, en este caso 6.
Esas personas están numeradas del 0 al 5.
Las siguientes 6 lineas (que es el numero de personas) describe la relación entre ellas.
El primer numero es el numero de conocidos, llamémoslo “m”, seguido de “m” números que representan a sus conocidos.
2 1 2 es el primer renglón, por lo tanto esta haciendo referencia al nodo 0 y esta conoce a 2 personas, que es la persona 1 y la persona 2.
Esto se repite para todos los demás y se ilustra la relación en la siguiente imagen:

La relación entre las personas no es bidireccional.
No por que la persona “x” conozca a la persona “y”, “y” conoce a la persona “x”.
De ahí vienen 3 consultas, seguido de 3 números, que nos indica desde que nodo sale la noticia.

La primera consulta sale del nodo 0.
El día 1 los conocidos de 0 se enteran de la noticia que son 1 y 2.
El día 2 los conocidos de 1 y 2 que no sepan la noticia se enteran que son 3 4 y 5.

Como ya todos conocen la noticia, termina el algoritmo y nos regresa que el día 2 se enteraron 3 personas.
Cuando no se entera ninguna persona se imprime un cero, que es el segundo caso de prueba que parte del numero 4.

Código en C++

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: