Arche Minus – Regional event 2015

Level 6

Énoncé

Joseph a fait un rêve pour le moins perturbant. Son ancêtre (Noé Marchand) revenait pour hanter ses nuits. En effet, lors d'une prémonition, Noé a vu que son terrain allait être inondé. Il fait alors appel à vous pour sauver ses animaux (et ensuite les revendre).

Le problème est qu'il n'a que très peu de temps et de matériaux. En particulier, il ne peut construire qu'une arche très petite (« minus » dans ses termes) et donc sans cloison. Mais le fait est que certains de ses animaux sont les prédateurs d'autres de ses animaux. Ainsi, il veut embarquer le maximum d'espèces telles qu'aucune espèce n'est la proie d'une autre dans l'embarcation.

Noé a tout de même remarqué deux choses concernant ses animaux. Premièrement, chacune de ses espèces est la proie d'exactement une autre espèce. Deuxièmement, toutes les espèces font partie d'un même groupe alimentaire (toutes les espèces sont reliées entre elles par des liens de prédateur à proie, voir le quatrième exemple).

Attention, si vous échouez votre famille ne sera pas financièrement prospère et vous risquez de briser le continuum espace-temps.

Entrée

La première ligne contient un entier n qui est le nombre d'espèces dont Noé dispose.

La ligne suivante contient n entiers. Le i-ème entier est l'indice du prédateur de la i-ème espèce (à partir de 0).

Sortie

La sortie est le nombre maximum d'espèces que Noé peut sauver à bord de son arche.

Contraintes

1 < n ≤ 50 000

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
6
1 2 3 4 5 0
Sample output
3
Note

Ici, Noé peut par exemple embarquer les espèces numérotées 0, 2 et 4.

Sample input
6
1 2 0 4 5 0
Sample output
3
Note

Dans cet exemple, Noé peut par exemple embarquer les espèces numérotées 1, 3 et 5.

Sample input
6
1 0 0 0 0 0
Sample output
5
Note

Pour ce troisième exemple, Noé peut embarquer les espèces numérotées 1, 2, 3, 4 et 5.

Sample input
4
1 0 0 1
Sample output
2
Note

Vous pouvez constater que l'espèce n°3 n'est aucunement un prédateur pour l'espèce n°2 (ni un prédateur d'un prédateur d'un prédateur…), cependant elles font partie du même groupe alimentaire car elles sont liées par les espèces numérotées 0 et 1.

Submit your solution

You have to register or log in to be able to submit your solution.