クラスカル法

最小全域木問題に対してのクラスカル法による解法
AOJ GRL 2_A Minimum Spanning Tree

・重みを持つすべての辺をコスト順に並び替える
・コストの低い辺から順に採用するか検討していく
・その辺を採用すると「閉路」ができてしまうなら採用しない
・「閉路」ができてしまうかどうかはunionfindで判定する
・点の数-1個の辺を採用したところで最小全域木が完成する

・問題文が、
点_I　　点_j　　コスト
点_i+1　点_j+1　コスト
となっているときに使いやすい

#入力
v,e = map(int,input().split())
costs,edges = [],[]
for _ in range(e):
  s,t,w = map(int,input().split())
  costs.append(w)
  edges.append([s,t])
ans = 0

##UnionFind-->>##
par = [-1]*v
siz = [1]*v

def root(x):
  if par[x] == -1:
    return x
  else:
    par[x] = root(par[x])
    return par[x]

def size(x):
  return siz[root(x)]

def unite(x,y):
  x = root(x)
  y = root(y)
  if x == y:
    return False
  if siz[x] >= siz[y]:
    par[y] = x
    siz[x] += siz[y]
  else:
    par[x] = y
    siz[y] += siz[x]
  return True

def issame(x,y):
  tf = root(x) == root(y)
  return tf
##-->>UnionFind##

#辺の並び替え　ここに計算コストO("e"log"e")
costs,edges = zip(*sorted(zip(costs,edges)))
#keyは採用した辺の数を格納する。これがv-1になるまで繰り返す
key = 0
for edge,cost in zip(edges,costs):
  s,t = edge
  #sとtが既に連結していればスキップ
  if issame(s,t):
    continue
  #そうでなければsとtを連結させてkeyを1つ増やす
  unite(s,t)
  key += 1
  ans += cost
  if key == v-1:
    print(ans)
    exit()