Bonjour!
J'aaurais voulu une petite aide de votre part. Je suis au canada, je fais de l'algo et j'ai zape tous mes cours en france, mais bon avec internet c'est qu'un detail.
J' ai un algo a poser qui doit etre le suivant:
 
Des mecs ont des papillons qu'il ont compare et auquelles ils ont donnes par pair un label: SAME si c'est les meme DIFFERENT sinon.
en gros, si ils ont ramenes 4 papillons, ils peuvent avoir ca: (1,2)=S , (2,3)=S, (3,4)=D, ....
Le but etant que je teste si ce au4il ont fait est consistent car si on a (1,2)=S , (2,3)=S et (1,3)=D ca va pas car si 1 et 2 pareil, 2 et 3 pareil alors 1 et 3 doivent etre pareil.
 
Y a la methode brut de tout comparer et voir si ca marche mais mon algo serait dans ce cas en O(n^2) or il me le faut en O(n+m) ou n est le nb de papillons et m les paires differentes en prenant en compte (x,y)=(y,x). Donc pour mon exemple, 4 papillons et 6 paires differentes.
 
Je pense utiliser un graph en mettant les 6 paires dans une queue ou une pile et representer par des noeuds les papillons et les cotes entre des noeuds si les deux noeuds relies ( donc les papillons) sont ds la meme categorie.
 
 
Voila j'ai reussi a modeliser le truc, mais pas possible de trouver le pseudocode aui convient a implementer ca, dois-je faire une recherche en profondeur, largeur???
 
 
Merci

J'aurais défini des groupes d'équivalence.
 
Un papillon ne peut être présent que dans un seul group d'équivalence.
 
En utilisant un tableau pour y mettre les doublets (papillon -> groupe) et un tableau dynamique de listes (groupe->liste des papillons du groupe), tu devrais t'en sortir.
 
Tu traites d'abord les couples de papillons identiques (S), en les triant préalablement par (numéro minimum du couple, numéro maximum du couple).
Quand tu ajoute un couple de papillons identiques à la structure, tu vérifie d'abord si l'un et/ou l'autre a déjà un groupe. Si ils ont tous deux un groupe, tu vérifie que ce groupe est le même sinon tu merge les groupes (en leur donnant le même numéro et en parcourrant la liste la plus courte pour changer le groupe des papillons s'y trouvant puis en concaténant les listes et en supprimant le groupe en trop) [***]. Si l'un deux seulement a un groupe, tu recopie le groupe pour l'autre. Si aucun a un groupe, tu crée un nouveau groupe pour les deux.
 
Puis tu traites les couples de papillons différents (D). Si ils ont été assignés tous deux à un groupe différents c'est bon.
 
Algo en O(n + m*ln(m)) avec un tri rapide, peut descendre en O(n+m) avec un tri par paquet.
 
*** Note: cette étape de merge ne devrait jamais arriver si les papillons sont triés.

Je sais qu'il existe des algorithmes dans les graphes nommés "réduction transitive". Cela concerne de très près ton problème .
Je ne peux pas t'en dire plus, ca remonte à deux ans cette notion    
 
Maintenant la compléxité, je ne la connais pas   .