On veut étudier un réseau de neurones. Ce réseau est décrit par un tableau de listes de la façon suivante : Chaque neurone est numéroté de manière unique entre 0 et (n-1). Le tableau contient n cases, chacune correspondant au neurone de même numéro. La case i contient la liste des neurones vers lesquels le neurone i émet des impulsions.
Lorsqu'un neurone reçoit une impulsion, il renvoi automatiquement une impulsion à son tour à tous les neurones de sa liste.
On cherche à connaître le nombre minimal de neurones qu'il faut pour qu'une impulsion partie de l'un d'entre eux finisse par revenir sur lui.
Soit un réseau de n neurones numérotés de 0 à (n-1) et décrit par un tableau de listes de la façon suivante : Il existe une connexion allant du neurone i jusqu'au neurone j si et seulement si l'entier j est dans la liste contenue dans la case i du tableau.
On appelle chemin de taille k dans un tel réseau une liste de neurones [n_1;n_2;...;n_k] telle qu'il existe une connexion reliant tout n_i à n_(i+1) (pour i variant de 1 à k-1). La longueur d'un tel chemin est k-1. Un tel chemin est un cycle si n_1 = n_k.
Étant donné un réseau tel que décrit précédemment, déterminer la longueur de son cycle (non nul) le plus court.
L'entrée comporte dans un premier temps le nombre de neurones, puis ligne par ligne les différentes cases du tableau, avec pour chaque case la liste d'entiers correspondant aux neurones en aval, séparés par des espaces. Cette liste ne sera jamais vide.
Le nombre de neurones est inférieur à 300.
Il y aura toujours au moins un cycle et sa longueur sera suffisamment raisonnable pour qu'un algorithme bien pensé trouve la solution dans un temps lui aussi raisonnable.Attention à la complexité de vos algorithmes !
La sortie est l'entier correspondant à la longueur du plus court cycle existant dans ce réseau. Cette valeur sera suivie d'un saut à la ligne.
entrée :
3 1 2 0
sortie :
3
entrée :
3 0 1 2 0 1 2 0 1 2
sortie :
1
Squelettes de codes :
[GROUPFULL:skeleton]