Retransmisión de mensajes.
Las vacas del granjero John están convenientemente numeradas del
al
.
Utilizando un mecanismo de comunicación anticuado basado en latas y cuerdas, las vacas han descubierto cómo comunicarse entre sí sin que el granjero John se dé cuenta.
Cada vaca puede reenviar mensajes a una sola vaca como máximo: para la vaca , el valor
indica el índice de la vaca a la que la vaca i reenviará cualquier mensaje que reciba (este número siempre es diferente de i). Si
es cero, la vaca i no reenvía mensajes.
Desafortunadamente, las vacas se han dado cuenta de la posibilidad de que los mensajes originados por ciertas vacas puedan quedar atrapados en bucles, reenviándose indefinidamente. Se dice que una vaca está "en bucle" si un mensaje enviado desde ella termina quedando atrapado en un bucle. Las vacas quieren evitar enviar mensajes desde vacas con problemas de comunicación. Ayúdalas contando el número total de vacas de FJ que no tienen problemas de comunicación.
Entrada
- Línea 1: El número de vacas,
.
- Líneas 2 a 1+N: La línea i+1 contiene el valor de
.
Salida
El número total de vacas que no tienen problemas de comunicación.
Ejemplo de Entrada
5
0
4
1
5
4
Detalles de la Entrada: Hay 5 vacas. La vaca 1 no reenvía mensajes. La vaca 2 reenvía mensajes a la vaca 4, y así sucesivamente.
Ejemplo de Salida
2
Detalles de la Salida: La vaca 1 no tiene problemas de comunicación, ya que no reenvía mensajes. La vaca 3 tampoco está loca, ya que reenvía los mensajes a la vaca 1, quien luego no los reenvía. Todas las demás vacas están locas.
USACO 2013 February Contest, Bronze. Problem 1. Message Relay.
Comments