Retransmisión de mensajes.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type

Las N vacas del granjero John están convenientemente numeradas del 1 al N.

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 i, el valor F(i) 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 F(i) 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, N (1 \leq N \leq 1000).
  • Líneas 2 a 1+N: La línea i+1 contiene el valor de F(i).

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

There are no comments at the moment.