# Exercice Star:

On considère un groupe de n personnes (n > 1). On peut demander à une personne A si elle connaît une personne B: soit elle la connaît, soit elle ne la connaît pas.
Ainsi chaque personne à un ensemble de personnes qu'elle connaît et de personnes qu'elle ne connaît pas (cependant, pour chaque personne, nous l'ignorons).
Une star est une personne qui ne connaît personne, mais que tout le monde connaît.

1) Combien peut-il y avoir de stars parmis n personnes ?
2) Déterminer un algorithme de complexité linéaire permettant de retrouver l'(les) éventuelle(s) star(s) au sein d'un groupe de n personnes, et donner le nombre de questions posées (la complexité donc) en fonction de n; évidemment le challenge c'est de trouver le plus efficace !(modifié)
[10:10]

Je crédite: c'est un exo trouvé sur une fiche de l'ENS Lyon en libre accès (mais c'est accessible pour des futurs sups)

Et petite précision: j'insiste sur le fait que la seul opération possible c'est de demander à X s'il connaît Y

### Solution proposée

1) Il peut n'y avoir aucune star parmi un groupe de n personne
Par contre s'il y en a une, elle est unique car sinon cela est absurde :
Avoir plus d'une star vooudrait dire que ces stars ne se connaissent pas pourtant elles sont connues de tous, ce qui se contredit.

2) En compléxité linéaire on a l'algorithme suivant O(2N) :

En pseudo-code:

stars_potentiels <- groupe
persA <- groupe[0]
connue <- Faux
Tant que connue est faux alors:
|    persB <- stars_potentiels[0]
|    Si persA est persB 
|    |    Si stars_potentiels ne contient que persB alors:
|    |    |    Pour chaque persC dans groupe:
|    |    |    |    Si persA n'est persC :
|    |    |    |    |    Si persC ne connait pas persA ou que persA connait persC:
|    |    |    |    |    |    Retirer persA de stars_potentiels
|    |    |    |    |    |    Continuer
|    |    |    connue <- Vrai
|    |    PersB est déplacé en fin de la liste stars_potentiels
|    |    Continuer
|    Si persA connait persB alors:
|    |    Retirer persA de stars_potentiels 
|    |    persA <- persB
|    Sinon:
|    |    Retirer persB de stars_potentiels
|    connue <- stars_potentiels vide?
Afficher stars_potentiels

En python:

matrix = [[..],..,[..]] # Matrice d'adjacence des liens de connaissances entre nos personnes

stars_potentiels = [i for i in range(len(matrix))] # Les personnes sont nommées par un nombre allant de 1 à n
persA = 0 # On prend la permière personne dans la liste
while len(stars_potentiels) > 0:
    persB = stars_potentiels[0]
    if persA == persB:
        if len(stars_potentiels) == 1 :
            for persC in range(len(matrix)):
                if persA != persC:
                    if matrix[persC][persA] == 0:
                        stars_potentiels.pop(0)
                        break
            break
        stars_potentiels.append(stars_potentiels.pop(0))
        continue;
    if matrix[persA][persB] == 1:
        # persA connait persB
        stars_potentiels.remove(persA)
        persA = persB
    else:
        # persA ne connait pas persB
        stars_potentiels.pop(0)
print(stars_potentiels)