edges = [
("Pe", "T", 13),
("Pe", "N", 68),
("Pe", "M", 78),
("Pe", "L", 51),
("Pe", "Pa", 51),
("T", "N", 68),
("T", "M", 70),
("T", "L", 60),
("T", "Pa", 61),
("N", "M", 21),
("N", "L", 35),
("N", "Pa",36),
("M", "L", 56),
("M", "Pa", 57),
("L", "Pa", 21),
]
class UnionFind:
def init(self, n):
self.parent = list(range(n))
self.rank = [0] * n

def find(self, u):  
    if self.parent[u] != u:  
        self.parent[u] = self.find(self.parent[u])  
    return self.parent[u]  

def union(self, u, v):  
    root_u = self.find(u)  
    root_v = self.find(v)  
    if root_u != root_v:  
        if self.rank[root_u] > self.rank[root_v]:  
            self.parent[root_v] = root_u  
        elif self.rank[root_u] < self.rank[root_v]:  
            self.parent[root_u] = root_v  
        else:  
            self.parent[root_v] = root_u  
            self.rank[root_u] += 1  

def kruskal(edges):
edges.sort(key=lambda edge: edge[2])
uf = UnionFind(len(set(city for edge in edges for city in edge[:2])))
mst = []

for u, v, weight in edges:  
    if uf.find(u) != uf.find(v):  
        uf.union(u, v)  
        mst.append((u, v, weight))  
  
return mst  

city_map = {
"Pe": 0, "T": 1, "N": 2, "M": 3, "L": 4, "Pa": 5
}

edges_with_indices = [(city_map[u], city_map[v], weight) for u, v, weight in edges]

mst_edges = [(list(city_map.keys())[u], list(city_map.keys())[v], weight) for u, v, weight in kruskal(edges_with_indices)]

print("最小生成树的边:")
for u, v, weight in mst_edges:
print(f"{u} - {v}: {weight}")

2023310143007