class UnionFind:
    def __init__(self, elementos):
        """
        Inicializa la estructura Union-Find.

        :param elementos: Iterable que contiene los elementos (nodos) del grafo
        """
        self.padre = {elemento: elemento for elemento in elementos}
        self.rango = {elemento: 0 for elemento in elementos}

    def encontrar(self, u):
        """
        Encuentra la raíz del conjunto en el que se encuentra el elemento u.

        :param u: Elemento para el cual se quiere encontrar la raíz
        :return: La raíz del conjunto
        """
        if self.padre[u] != u:
            self.padre[u] = self.encontrar(self.padre[u])
        return self.padre[u]

    def unir(self, u, v):
        """
        Une dos conjuntos.

        :param u: Elemento del primer conjunto
        :param v: Elemento del segundo conjunto
        """
        raiz_u = self.encontrar(u)
        raiz_v = self.encontrar(v)

        if raiz_u != raiz_v:
            if self.rango[raiz_u] > self.rango[raiz_v]:
                self.padre[raiz_v] = raiz_u
            elif self.rango[raiz_u] < self.rango[raiz_v]:
                self.padre[raiz_u] = raiz_v
            else:
                self.padre[raiz_v] = raiz_u
                self.rango[raiz_u] += 1

def kruskal(grafo):
    """
    Implementación del Algoritmo de Kruskal para encontrar el árbol generador mínimo.
    
    :param grafo: Diccionario que representa el grafo ponderado conexo no dirigido,
                  donde las claves son los nodos y los valores son listas de tuplas (vecino, peso)
    :return: Lista de aristas que forman el árbol generador mínimo
    """
    # Convertir el grafo a una lista de aristas con (peso, u, v)
    aristas = []
    for u in grafo:
        for v, peso in grafo[u]:
            if (peso, v, u) not in aristas:  # Asegurarse de que cada arista se agregue solo una vez
                aristas.append((peso, u, v))
    
    # Ordenar las aristas según su peso
    aristas.sort()

    # Inicializar la estructura Union-Find
    uf = UnionFind(grafo.keys())

    # Algoritmo de Kruskal
    agm = []
    for peso, u, v in aristas:
        if uf.encontrar(u) != uf.encontrar(v):
            uf.unir(u, v)
            agm.append((u, v, peso))

    return agm

# Ejemplo 1 (pág. 642 K. Rosen) / Solución Figura 2 (pág. 643 K. Rosen)
ciudades = {
    'San Francisco': [('Denver', 900), ('Chicago', 1200), ('Nueva York', 2000), ('Atlanta', 2200)],
    'Denver': [('San Francisco', 900), ('Chicago', 1300), ('Nueva York', 1600), ('Atlanta', 1400)],
    'Chicago': [('San Francisco', 1200), ('Denver', 1300), ('Nueva York', 1000), ('Atlanta', 700)],
    'Nueva York': [('San Francisco', 2000), ('Denver', 1600), ('Chicago', 1000), ('Atlanta', 800)],
    'Atlanta': [('San Francisco', 2200), ('Denver', 1400), ('Chicago', 700), ('Nueva York', 800)]
}

# Ejemplo 2 (pág. 642 K. Rosen) / Solución Figura 5 (pág. 644 K. Rosen)
grafo = {
    'a': [('b', 2), ('e', 3)],
    'b': [('a', 2), ('c', 3), ('f', 1)],
    'c': [('b', 3), ('d', 1), ('g', 2)],
    'd': [('c', 1), ('h', 5)],
    'e': [('a', 3), ('f', 4), ('i', 4)],
    'f': [('b', 1), ('e', 4), ('g', 3), ('j', 2)],
    'g': [('c', 2), ('f', 3), ('h', 3), ('k', 4)],
    'h': [('d', 5), ('g', 3), ('l', 3)],
    'i': [('e', 4), ('j', 3)],
    'j': [('f', 2), ('i', 3), ('k', 3)],
    'k': [('g', 4), ('j', 3), ('l', 1)],
    'l': [('h', 3), ('k', 1)],
}

# Encontrar el árbol generador mínimo
agm_ciudades = kruskal(ciudades)
print("Componentes del Árbol de Expansión Mínima (Ejemplo 1):")
for u, v, peso in agm_ciudades:
    print(f"{u} - {v}: {peso}")
print()
agm = kruskal(grafo)
print("Componentes del Árbol de Expansión Mínima (Ejemplo 2):")
for u, v, peso in agm:
    print(f"{u} - {v}: {peso}")