题解 | 【模板】最小生成树

import sys


class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n + 1))  # 顶点编号从1开始
        self.rank = [0] * (n + 1)

    def find(self, x):  # 找出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 self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        else:
            self.parent[root_y] = root_x
            if self.rank[root_x] == self.rank[root_y]:  # 深度+1
                self.rank[root_x] += 1
        return True

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)


def main():
    n, m = map(int, sys.stdin.readline().split())
    edges = []
    for i in range(m):
        u, v, w = map(int, sys.stdin.readline().split())
        # 按照 u,v，w 顺序存
        edges.append((u, v, w, i + 1))  # 边的编号
    # 按照权重升序排序边 指定按照第三个元素w 排序
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    total_wait = 0
    mnt_edges = []
    # 遍历排序的边构建最小生成树
    for u, v, w, idx in edges:
        if not uf.is_connected(u, v):
            if uf.union(u, v):
                total_wait += w
                #mnt_edges.append([u, v, w, idx])
                mnt_edges.append(idx)
                if len(mnt_edges) == n - 1:  # 当边数为n-1
                    break
    print(total_wait)
    print(" ".join(map(str, mnt_edges)))


main()