SW VI : Les Ewoks sont tous copains

Les Ewoks sont des êtres très sociables. Tout le monde le sait. Pour chaque Ewok, un ami d'un de ses amis est son ami. Précisément, un Ewok a des amis de premier cercle, ses amis directs ou 1-amis. Un ami direct d'un des 1-amis d'un Ewok, s'il n'est pas lui même un 1-ami, est un 2-ami. En règle générale 2 Ewoks A et B sont n-amis s'il existe un Ewok C, 1-ami de A (ami direct), qui est aussi (n-1)-ami de B, et qu'il n'existe pas de chemin plus court les reliant (via un autre ami).

Voici un exemple :

Molosha est ami avec Junhexmo
Junhexmo est ami avec Bimolo
et Bimolo est ami avec Patbimo

S'il n'existe pas de lien plus direct entre Molosha et Patbimo, alors ils sont 3-amis. Mais si Junhexmo, par exemple, était aussi l'ami direct de Patbimo, alors Molosha et Patbimo seraient 2-amis.

Dans une tribu Ewok, on a pu recenser tous les couples de 1-amis qui existent. Les Ewoks sont tellement sociables que finalement chacun d'eux est n-ami avec chacun pour un certain n donné. L'objectif, afin de rallier la tribu à votre cause est d'identifier les amis les plus éloignés, afin de les rapprocher en les présentant directement les uns aux autres et ainsi renforcer la cohésion du groupe.

Vous savez que dans cette tribu, il y a des couples de 8-amis, mais vous ignorez combien : ce sont les couples qui se connaissent le moins. Identifiez tous les Ewoks faisant partie de ces couples, et donnez en la liste (chaque nom ne doit figurer qu'une seule fois). Par exemple :

"Molosha", "Junhexmo", "Bimolo", "Patbimo"
Ce problème est tiré de c0d1ng UP 2018

Type de retour

une séquence de chaînes de caractères

Entrée du problème

Lien vers les données d'entrée

Formulaire de réponse

Vous devez être connecté pour pouvoir répondre aux défis

Tags : graphe cup18