"""
TORNIOR Alexis NSI TG3 DM_Kruskal

"""

class Graph:
    def __init__(self, sommet):
        """Constructeur"""
        self.S = sommet
        self.graph = []
 
    def ajouter_arete(self,sommet1, sommet2 , p):
        """Ajooute une arete avec les deux sommets de l'arete et son poid"""
        self.graph.append([sommet1,sommet2, p])
 
 
    def recherche(self, parent, arete_selectione):
        """Recherche le parent de l'arete et le renvoie , tant qu'il ne le trouve pas cette fonction se repete,recursivite""" 
        if parent[arete_selectione] == arete_selectione:
            return arete_selectione
        return self.recherche(parent, parent[arete_selectione])
    
    def __repr__(self):
        """Permet d'afficher le graph"""
        return str(self.graph)
 
    def union(self, parent, position, A, B):
        """Vas chercher et modifie les parents de l'arete en fonction du nombre d'arete que le parent compte deja"""
        racine_parent_A = self.recherche(parent, A)
        racine_parent_B = self.recherche(parent, B)
        if position[racine_parent_A] < position[racine_parent_B]:
            parent[racine_parent_A] = racine_parent_B
        elif position[racine_parent_A] > position[racine_parent_B]:
            parent[racine_parent_B] = racine_parent_A
        else:
            parent[racine_parent_B] = racine_parent_A
            position[racine_parent_A] += 1
    
    def kruskal(self):
        """Effectue l'algorithme de Kruskal qui tri les aretes du graph par poids et juge si il les ajoute ou pas ,
        il renvoie Les  aretes et leur poids qu'il faut rajouter dans l'ordre pour obtenir le graph de poids minimale """
        resultat = []
        compteur1 , compteur2 = 0, 0
        self.graph = sorted(self.graph, key=lambda item: item[2])
        parent = []
        position = []
        for noeud in range(self.S):
            parent.append(noeud)
            position.append(0)
        while compteur2 < self.S - 1:
            sommet1, sommet2, p = self.graph[compteur1]
            compteur1 +=1
            racine_parent_A = self.recherche(parent, sommet1)
            racine_parent_B = self.recherche(parent, sommet2)
            if racine_parent_B != racine_parent_A:
                compteur2 += 1
                resultat.append([sommet1, sommet2, p])
                self.union(parent, position, racine_parent_A, racine_parent_B)
        for sommet1,sommet2 , poids in resultat:
            print("arete:",sommet1, sommet2,end =" ")
            print("-",poids)
        

G=Graph(5)
G.ajouter_arete(0, 1, 8)
G.ajouter_arete(0, 2, 5)
G.ajouter_arete(1, 2, 9)
G.ajouter_arete(1, 3, 11)
G.ajouter_arete(2, 3, 15)
G.ajouter_arete(2, 4, 10)
G.ajouter_arete(3, 4, 7)


print(G)
G.kruskal()