Arche Minus – Épreuve régionale 2015

Niveau 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

Contraintes d'exécution

Utilisation mémoire maximum
10000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
6
1 2 3 4 5 0
Exemple de sortie
3
Commentaire

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

Exemple d'entrée
6
1 2 0 4 5 0
Exemple de sortie
3
Commentaire

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

Exemple d'entrée
6
1 0 0 0 0 0
Exemple de sortie
5
Commentaire

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

Exemple d'entrée
4
1 0 0 1
Exemple de sortie
2
Commentaire

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.