import heapq

# Un arbre couvrant minimum (Minimum Spanning Tree) relie tous les sommets d'un graphe
# NON ORIENTÉ pondéré avec le poids total minimal, sans former de cycle.

# --- Kruskal : trie toutes les arêtes, ajoute la moins chère si elle ne crée pas de cycle ---
class UnionFind:
    def __init__(self, elements: list[str]):
        self.parent = {e: e for e in elements}
        self.rang = {e: 0 for e in elements}

    def trouver(self, x: str) -> str:
        # compression de chemin : aplatit l'arbre pour accélérer les appels futurs
        if self.parent[x] != x:
            self.parent[x] = self.trouver(self.parent[x])
        return self.parent[x]

    def union(self, x: str, y: str) -> bool:
        racine_x, racine_y = self.trouver(x), self.trouver(y)
        if racine_x == racine_y:
            return False   # déjà dans le même ensemble -> ajouter cette arête créerait un cycle
        # union par rang : accroche le plus petit arbre sous le plus grand
        if self.rang[racine_x] < self.rang[racine_y]:
            racine_x, racine_y = racine_y, racine_x
        self.parent[racine_y] = racine_x
        if self.rang[racine_x] == self.rang[racine_y]:
            self.rang[racine_x] += 1
        return True

def kruskal(sommets: list[str], aretes: list[tuple[float, str, str]]) -> tuple[list, float]:
    # Complexité : O(E log E) dominé par le tri des arêtes
    aretes_triees = sorted(aretes)   # tri par poids croissant
    uf = UnionFind(sommets)
    mst = []
    poids_total = 0.0

    for poids, a, b in aretes_triees:
        if uf.union(a, b):        # ajoute l'arête seulement si elle ne crée pas de cycle
            mst.append((a, b, poids))
            poids_total += poids
        if len(mst) == len(sommets) - 1:
            break   # un MST a exactement V-1 arêtes -- on peut s'arrêter

    return mst, poids_total

sommets = ["A", "B", "C", "D"]
aretes = [(1, "A", "C"), (4, "A", "B"), (2, "C", "B"), (5, "C", "D"), (1, "B", "D")]
mst, poids = kruskal(sommets, aretes)
assert poids == 4   # A-C (1) + B-D (1) + C-B (2) = 4

# --- Prim : fait croître un arbre depuis un sommet de départ, ajoute toujours l'arête la moins chère ---
def prim(graphe: dict[str, list[tuple[str, float]]], depart: str) -> tuple[list, float]:
    # Complexité : O(E log V) avec un tas binaire -- généralement plus rapide sur graphe DENSE
    visites = {depart}
    file_priorite = [(poids, depart, voisin) for voisin, poids in graphe[depart]]
    heapq.heapify(file_priorite)
    mst = []
    poids_total = 0.0

    while file_priorite and len(visites) < len(graphe):
        poids, origine, destination = heapq.heappop(file_priorite)
        if destination in visites:
            continue   # les deux extrémités sont déjà dans l'arbre -- créerait un cycle
        visites.add(destination)
        mst.append((origine, destination, poids))
        poids_total += poids

        for voisin, w in graphe.get(destination, []):
            if voisin not in visites:
                heapq.heappush(file_priorite, (w, destination, voisin))

    return mst, poids_total

graphe_non_oriente = {
    "A": [("C", 1), ("B", 4)],
    "B": [("A", 4), ("C", 2), ("D", 1)],
    "C": [("A", 1), ("B", 2), ("D", 5)],
    "D": [("B", 1), ("C", 5)],
}
mst_prim, poids_prim = prim(graphe_non_oriente, "A")
assert poids_prim == 4   # même poids total optimal que Kruskal, chemin de construction différent