最小生成树 MST

 Kruskal MST

模板：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return

        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1

def kruskal(n, edges):
    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(n)
    mst_w = 0
    mst_edges= []
    for u, v, w in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst_w += w
            mst_edges.append((u, v, w))
    return mst_w, mst_edges

n, m = map(int, input().split())
edges = []
for i in range(m):
    a, b, w = map(int, input().split())
    edges.append((a - 1, b - 1, w))
mst_w, mst_edges = kruskal(n, edges)
if len(mst_edges) != n - 1:
    print('orz')
else:
    print(mst_w)