A67 - MST (Minimum Spanning Tree)
解答
code: python
# Union-Find 木
class unionfind:
# n 頂点の Union-Find 木を作成
# （ここでは頂点番号が 1-indexed になるように実装しているが、0-indexed の場合は par, size のサイズは n でよい）
def __init__(self, n):
self.n = n
self.par = -1 * (n + 1) # 最初は親が無い self.size = 1 * (n + 1) # 最初はグループの頂点数が 1 # 頂点 x の根を返す関数
def root(self, x):
# 1 個先（親）がなくなる（つまり根に到達する）まで、1 個先（親）に進み続ける
return x
# 要素 u, v を統合する関数
def unite(self, u, v):
rootu = self.root(u)
rootv = self.root(v)
if rootu != rootv:
# u と v が異なるグループのときのみ処理を行う
else:
# 要素 u と v が同一のグループかどうかを返す関数
def same(self, u, v):
return self.root(u) == self.root(v)
N, M = map(int, input().split())
# 辺を長さの小さい順にソートする
edges.sort(key = lambda x: x2) # 最小全域木を求める
uf = unionfind(N)
answer = 0
for a, b, c in edges:
if not uf.same(a, b):
uf.unite(a, b)
answer += c
print(answer)