Problem:


Minimum Spanning Tree

Find the sum of weights of edges of the Minimum Spanning Tree for a given weighted undirected graph G = (V, E).

Input

|V| |E|
s0 t0 w0
s1 t1 w1
:
s|E|-1 t|E|-1 w|E|-1

, where |V| is the number of vertices and |E| is the number of edges in the graph. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively.

si and ti represent source and target verticess of i-th edge (undirected) and wi represents the weight of the i-th edge.

Output

Print the sum of the weights of the Minimum Spanning Tree.

Constraints

1 ≤ |V| ≤ 10,000

0 ≤ |E| ≤ 100,000

0 ≤ wi ≤ 10,000

The graph is connected

There are no parallel edges

There are no self-loops

Sample Input 1

4 6
0 1 2
1 2 1
2 3 1
3 0 1
0 2 3
1 3 5

Sample Output 1

3

Sample Input 2

6 9
0 1 1
0 2 3
1 2 1
1 3 7
2 4 1
1 4 3
3 4 1
3 5 1
4 5 6

Sample Output 2

5



Sample input:
4 6
0 1 2
1 2 1
2 3 1
3 0 1
0 2 3
1 3 5


Sample output:
3

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

V, E = map(int, input().split())

edges = defaultdict(list)

for _ in range(E):
    s, t, w = map(int, input().split())
    edges[s].append((t, w))
    edges[t].append((s, w))

in_tree = [False] * V
ans = 0
start = 0
in_tree[start] = True

q = [(w, start, t) for t, w in edges[start]]
heapq.heapify(q)

while q:
    w, s, t = heapq.heappop(q)
    if in_tree[s] == in_tree[t]:
        continue
    ans += w
    in_tree[t] = True
    for tt, w in edges[t]:
        heapq.heappush(q, (w, t, tt))

print(ans)

Submission status: Accepted

Solution code:
# solve 64 by Kruskal algorithm

class UnionFind(object):
    def __init__(self, n):
        self.par = [-1] * n
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return False
        else:
            if self.par[x] > self.par[y]:
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x
            return True

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

    def size(self, x):
        return -self.par[self.find(x)]


# グラフの読み込み
from heapq import heappush, heappop
edges = []
N, M = map(int, input().split())
for _ in range(M):
    si, ti, wi = map(int, input().split())
    heappush(edges, (wi, si, ti))

# クラスカル法
uf = UnionFind(N)
cost = 0
mst = []
while len(edges) > 0:
    (w, u, v) = heappop(edges)
    if not uf.same(u, v):
        uf.unite(u, v)
        mst.append((u, v))
        cost += w

print(cost)
# print(mst)

Submission status: Accepted

Solution code:
import heapq
def prim_heap(v):
    used = [True] * v #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

v,e=map(int,input().split())
edge=[[] for _ in range(v)]
for i in range(e):
    s,t,w=map(int,input().split())
    edge[s].append((w,t))
    edge[t].append((w,s))
print(prim_heap(v))

Submission status: Accepted

Solution code:
# Union-Find木（サイズ付き）
class UnionFind():
    # 初めは全ての頂点が別々の木の根
    def __init__(self, n):  # n要素で初期化
        self.parent = [None] * n # 親
        self.rank = [None] * n   # 木の深さ
        self._size = [1] * n # 要素が属する集合の大きさ（根の要素のみ参照すること）
        for i in range(n):
            self.parent[i] = i
            self.rank[i] = 0

    def root_of(self, x):
        children = [x]
        while self.parent[x] != x:
            # px = self.parent[x]
            x = self.parent[x]
            children.append(x)

        for ch in children:
            self.parent[ch] = x

        return x

    # xとyの属する集合を併合
    def union(self, x, y):
        rx = self.root_of(x)
        ry = self.root_of(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]: # ランクの小さい木から大きい木の根に辺を張る
            self.parent[rx] = ry  # rxをryの子とする
            self._size[ry] += self._size[rx]
        else:
            self.parent[ry] = rx
            self._size[rx] += self._size[ry]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するかどうか
    def same(self, x, y):
        return self.root_of(x) == self.root_of(y)


def kruskal(E, n):
    '''
    E ... (辺のコスト, (始点, 終点))のリスト
    n ... 頂点の数
    '''
    E.sort()
    cost = 0
    uf = UnionFind(n)
    for c, (x, y) in E:
        if not uf.same(x, y):
            cost += c
            uf.union(x, y)
    return cost

n, m = [int(x) for x in input().split()]
E = []
for _ in range(m):
    s, t, w = [int(x) for x in input().split()]
    E.append((w, (s, t)))

print(kruskal(E, n))

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/problems/GRL_2_A
def root(x):
    if parent_map[x] == x:
        return x
    parent_map[x] = root(parent_map[x])
    return parent_map[x]


def same(x, y):
    return root(x) == root(y)


def unite(x, y):
    x = root(x)
    y = root(y)
    parent_map[x] = y


v, e = list(map(int, input().split()))
edges = [list(map(int, input().split())) for i in range(e)]
edges.sort(key=lambda x: x[2])
parent_map = [i for i in range(v)]

result = 0
for s, t, w in edges:
    if not same(s, t):
        result += w
        unite(s, t)
print(result)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter


class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n

    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.parent[x] > self.parent[y]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x

    def is_same(self, x, y):
        return self.root(x) == self.root(y)


def kruskal(n, edges):
    """クラスカル法によって最小全域木の重みを求める"""
    sorted_edges = sorted(edges, key=itemgetter(2))
    uf = UnionFind(n)
    res = 0
    for u, v, cost in sorted_edges:
        if not uf.is_same(u, v):
            uf.merge(u, v)
            res += cost
    return res


n, m = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(m)]


ans = kruskal(n, edges)
print(ans)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

v,e = mi()

path = []

for i in range(e):
    a = li()
    path.append([a[2], a[0], a[1]])

path.sort()

class UnionFind:
    def __init__(self,n):
        self.n = n
        self.d = [-1] * n

    def find(self, x):
        if(self.d[x] < 0):
            return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.d[x] > self.d[y]):
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

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

    def size(self,x):
        return -self.d[self.find(x)]

uf = UnionFind(v)

ans = 0
for i in path:
    w = i[0]
    s = i[1]
    t = i[2]
    if uf.same(s,t):
        pass
    else:
        uf.union(s,t)
        ans += w


print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        親が同じか判別する
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        yをxの根に繋ぐ
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        """
        xとyが同じ連結成分か判別する
        """
        return self.find(x) == self.find(y)

    def size(self, x):
        """
        xの連結成分の大きさを返す
        """
        return -self.parents[self.find(x)]

    def kruskal(self, edge):
        """
        :param edge: edge = [(コスト, 頂点1, 頂点2),...]の形で重み付き隣接リストを渡して下さい
        :return: 最小全域木のコストの和
        """
        edge.sort()
        cost_sum = 0
        for cost, node1, node2 in edge:
            if not self.same(node1, node2):
                cost_sum += cost
                self.union(node1, node2)
        return cost_sum


def resolve():
    V, E = map(int, input().split())
    edge = []
    for _ in range(E):
        s, t, w = map(int, input().split())
        edge.append([w, s, t])

    uf = UnionFind(V)
    res = uf.kruskal(edge)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
V, E = map(int, input().split())
inf = float('inf')
graphs = [list(map(int, input().split())) for _ in range(E)]
# コストが低い順に並べる
graphs.sort(key=lambda x: x[2])
# print(graphs)

nodes = [i for i in range(V)]
cost = 0


def root(node):
    if nodes[node] == node:
        return node
    nodes[node] = root(nodes[node])
    return nodes[node]


for i, j, k in graphs:
    if not root(i) == root(j):
        cost += k
        nodes[root(i)] = root(j)
print(cost)

Submission status: Accepted

Solution code:
v, e = map(int, input().split())

from heapq import heappush, heappop
edges = []
for _ in range(e):
    s, t, w = map(int, input().split())
    heappush(edges, (w, s, t))

# initialize
par = [-1] * v
rank = [0] * v
# Union Find Tree
def find(x):
    """ 根ノードの値を見つけて返す """
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x, y):
    """xとyを結合する"""
    rootx = find(x)
    rooty = find(y)

    if rootx == rooty:
        return False
    else:
        if rank[rootx] < rank[rooty]:
            par[rootx] = rooty
        else:
            par[rooty] = rootx
            if rank[rootx] == rank[rooty]: rank[rootx] += 1
        return True

def same(x, y):
    """ xとyが同じ集合に属しているか """
    return find(x) == find(y)

ans = 0
while edges:
    w, s, t = heappop(edges)
    if not same(s, t):
        ans += w
        unite(s, t)

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
        self.siz = [1 for i in range(n)]
    
    def find(self, x):
        if self.par[x] == x:
            return x
        return self.find(self.par[x])
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
            self.siz[x] += self.siz[y]
        else:
            self.par[x] = y
            self.siz[y] += self.siz[x]
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return self.siz[self.find(x)]
    
def kruskal(n, m):
    res = 0
    uf = UnionFind(n)
    for i in range(m):
        w, s, t = es[i]
        if uf.same(s, t):
            continue
        uf.unite(s, t)
        res += w
    return res

V, E = map(int, input().split())
es = []
for i in range(E):
    s, t, w = map(int, input().split())
    es.append([w, s, t])

es.sort(key=lambda x: x[0])
res = kruskal(V, E)
print(res)

Submission status: Accepted

Solution code:
class UF():
  def __init__(self, n):
    self.parents = [-1] * n

  def find(self,n):
    if self.parents[n] < 0:
      return n
    else:
      self.parents[n] = self.find(self.parents[n])
      return self.parents[n]

  def union(self, u, v):
    p1, p2 = self.find(u), self.find(v)
    if p1 == p2: return

    if self.parents[p1] > self.parents[p2]:
      p1,p2 = p2,p1

    self.parents[p1] += self.parents[p2]
    self.parents[p2] = p1

  def same(self, u, v):
    return self.find(u) == self.find(v)

V,E = map(int,input().split())
edges = []
for i in range(E):
  s,t,w = map(int,input().split())
  edges.append((w,s,t))
edges.sort(key=lambda x: x[0])

uf = UF(V)
ans = 0
for i in range(E):
  w,s,t = edges[i]
  if not uf.same(s,t):
    uf.union(s,t)
    ans += w

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.rank = [1]*n
    
    def root(self, x):
        if x == self.p[x]:
            return x
        self.p[x] = y = self.root(self.p[x])
        return y
    
    def unite(self, x, y):
        px = self.root(x); py = self.root(y)
        if px == py:
            return 0
        rx = self.rank[px]; ry = self.rank[py]
        if ry < rx:
            self.p[py] = px
        elif rx < ry:
            self.p[px] = py
        else:
            self.p[py] = px
            self.rank[px] += 1
        return 1

    def same(self, x, y):
        px = self.root(x); py = self.root(y)
        return px == py

V,E = list(map(int,input().split()))
STW = sorted([list(map(int,input().split())) for _ in range(E)],key=lambda x: x[2])

union_find = UnionFind(V+1)
ans = 0
for s,t,w in STW:
    if not union_find.same(s,t):
        ans += w
        union_find.unite(s,t)

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
            self.size[xRoot] += self.size[yRoot]
            self.size[yRoot] = 0
        else:
            self.parents[xRoot] = yRoot
            self.size[yRoot] += self.size[xRoot]
            self.size[xRoot] = 0

V,E = map(int,input().split())
tree = UnionFind(V)
edges = [list(map(int,input().split())) for _ in range(E)]
edges.sort(key=lambda x: x[2])
cost = 0
for s,t,w in edges:
    if tree.find(s) != tree.find(t):
        cost += w
        tree.unite(s,t)

print(cost)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        '''
        要素xが属するグループの根を返す
        '''
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        '''
        要素xが属するグループと要素yが属するグループとを併合する
        '''
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        '''
        要素xが属するグループのサイズ（要素数）を返す
        '''
        return -self.parents[self.find(x)]

    def same(self, x, y):
        '''
        要素x, yが同じグループに属するかどうかを返す
        '''
        return self.find(x) == self.find(y)

    def members(self, x):
        '''
        要素xが属するグループに属する要素をリストで返す
        '''
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        '''
        各要素の親要素の番号を格納するリスト
        '''
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        '''
        グループの数を返す
        '''
        return len(self.roots())

    def all_group_members(self):
        '''
        {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        '''
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def kruskal(v: int, edges: list):
    """
    v: 頂点数
    edges: 各辺のstart end weightのリスト
    """
    edges.sort(key=lambda edge: edge.weight)
    uf = UnionFind(v)
    mst = []
    for edge in edges:
        if not uf.same(edge.start, edge.end):
            uf.union(edge.start, edge.end)
            mst.append(edge)
    return mst

V, E = map(int, input().split())

from collections import namedtuple
Edge = namedtuple("Edge", ['start', 'end', 'weight'])
edges = []
for _ in range(E):
    s, t, w = map(int, input().split())
    edges.append(Edge(s, t, w))

mst = kruskal(V, edges)
print(sum([e.weight for e in mst]))

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
# list(map(int, input().split()))

class UnionFind(object):
    def __init__(self, n = 1):
        self.link = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

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

        # re-connect union find to make the height of tree lower
        # you can use while, but recursion makes it easier to reconnect
        self.link[x] = self.find(self.link[x])
        return self.link[x]

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

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

        if self.size[x] < self.size[y]:
            x, y = y, x
        self.link[y] = x
        self.size[x] += self.size[y]
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]


V, E = map(int, input().split())

edges = [0] * E
for i in range(E):
    s, t, w = map(int, input().split())
    edges[i] = (w, s, t)

u = UnionFind(V)

edges = sorted(edges)

ans = 0
for e in edges:
    w, s, t = e
    if u.is_same(s, t):
        continue
    u.unite(s, t)
    ans += w
print(ans)

Submission status: Accepted

Solution code:
v,e=map(int,input().split())
s=sorted([list(map(int,input().split()))for i in range(e)],key=lambda x:x[2])
d=[i for i in range(v)]
def f(x):
    if x==d[x]:
        return x
    d[x]=f(d[x])
    return f(d[x])
a=0
for i,j,h in s:
    i,j=f(i),f(j)
    if i!=j:
        d[i]=j
        a+=h
print(a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

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

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx != ry:
        par[rx] = ry

def same(x, y):
    return root(x) == root(y)

n, m = map(int, input().split())
E = []
for i in range(m):
    s, t, w = map(int, input().split())
    E.append([w, s, t])

E.sort()

par = [i for i in range(n)]

ans = 0

for e in E:
    if not same(e[1], e[2]):
        unite(e[1], e[2])
        ans += e[0]

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ
 
    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]
 
    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
 
    def is_same(self, x, y):  # x, y が同じ集合に属するか判定する
        return self.find(x) == self.find(y)
 
    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]

def kruskal(max_vertex,edges):
    edges.sort(key=lambda x:x[2])#costでソート
    uf=UnionFind(max_vertex)
    mst=[]
    for edge_cost in edges:
        es,ee,cost=edge_cost
        if not uf.is_same(es,ee):
            uf.unite(es,ee)
            mst.append([(es,ee),cost])
    return mst
         


#costでソートするから[頂点,頂点,重み]でもったほうがいいのでは
v,e=map(int,input().split())#v: 頂点の数 e:辺の数
graph=[]
for i in range(e):
    f,s,cost=map(int,input().split())
    graph.append([f,s,cost])#頂点0スタート

ans=0
for i in kruskal(v,graph):
    ans+=i[1]
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

class UnionFindTree:
    def __init__(self,size):
        self.rank=[0]*size
        self.p=[0]*size
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self,i):
        self.p[i]=i
        self.rank[i]=0
    
    def same(self,x,y):
        return self.findSet(x) == self.findSet(y)
    
    def unite(self, x,y):
        self.link(self.findSet(x), self.findSet(y))
    
    def link(self, x, y):
        if(self.rank[x] > self.rank[y]):
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y]+=1
     
    def findSet(self, x):
        if(x!=self.p[x]):
            self.p[x]=self.findSet(self.p[x])
        return self.p[x]

    def print(self):
        print(self.p)


def readinput():
    nv, ne=list(map(int,input().split()))
    nList=[]
    for _ in range(ne):
        s,t,w=list(map(int,input().split()))
        nList.append((s,t,w))
    return nv,ne,nList

def Kruskal(nv,nList):
    sortedList=sorted(nList, key=itemgetter(2))
    S=UnionFindTree(nv)
    K=[]

    for e in sortedList:
        s=e[0]
        t=e[1]
        if S.same(s,t)==False:
            S.unite(s,t)
            K.append(e)
    
    return K

def main(nv,ne,nList):
    K=Kruskal(nv,nList)
    total=0
    for e in K:
        total+=e[2]
    return total


if __name__=='__main__':
    nv,ne,nList=readinput()
    ans=main(nv,ne,nList)
    print(ans)

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    V, E = next(it), next(it)

    ee = [-1] * V
    def find(a):
        q = []
        while ee[a] >= 0:
            q.append(a)
            a = ee[a]
        for i in q:
            ee[i] = a
        return a
    def union(a, b):
        ai = find(a)
        bi = find(b)

        r1, r2 = ee[ai],  ee[bi]
        if r1 > r2:
            ai, bi = bi, ai

        ee[bi] = ai
        if r1 == r2:
            ee[ai] -= 1
    def same(a, b):
        ai = find(a)
        bi = find(b)

        return ai == bi

    ans = 0
    for si, ti, wi in sorted(zip(it, it, it), key=lambda x: x[2]):
        if same(si, ti):
            continue
        ans += wi
        union(si, ti)

    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
class Edge():
    def __init__(self, src, to, weight):
        self.src = src
        self.to = to
        self.weight = weight

    def __lt__(self, other):
        return self.weight < other.weight

class Edges():
    def __init__(self):
        self.E = []
    
    def append(self, src, to, weight=0):
        self.E.append(Edge(src, to, weight))

    def getInOrderByASC(self):
        return sorted(self.E)

class UnionFind():
    def __init__(self, N):
        self.N = N
        self.parents = [-1]*N

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
        
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


class MinimumSpanningTree():
    def __init__(self, V, edges):
        self.V = V
        self.E = edges

    # O(E*log(V))
    def kruskal(self):
        U = UnionFind(self.V)
        total = 0
        for e in self.E.getInOrderByASC():
            if not U.same(e.src, e.to):
                total += e.weight
                U.unite(e.src, e.to)
        return total


V,E = map(int, raw_input().split())
edges = Edges()
for i in range(E):
    s,t,w = map(int, raw_input().split())
    edges.append(s,t,w)

mst = MinimumSpanningTree(V, edges)
print mst.kruskal()

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
#setrecursionlimit(10**5)
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納
        # par[x]=xの時そのノードは根　
        self.par = [i for i in range(n + 1)]
        # rank
        self.rank = [0] * (n + 1)
        self.size = [1] * (n + 1)

    def find(self, x):
        # 根の番号を返す(所属する集合を確認する)
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def check(self, x, y):
        # x,yが同じ集合に属するかどうか調べる
        return self.find(x) == self.find(y)


    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        # rankの小さいものを大きいほうにくっつける
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def count_group(self, n):
        return len({self.find(x) for x in range(1, n + 1)})

v ,e = map(int, input().split())
stw = [list(map(int, input().split())) for i in range(e)]
stw.sort(key=lambda x:x[-1])
uf = UnionFind(v)

rec = 0
for s, t, w in stw:
    if not uf.check(s, t):
        uf.union(s, t)
        rec += w
print(rec)

Submission status: Accepted

Solution code:
# Union-Find部分
def find(x):
    global uf
    if uf[x]<0:
        return x
    else:
        uf[x] = find(uf[x])
        return uf[x]
    
def union(x, y):
    """
    Input: x, y
          x,y are vertex in tree.
    Return: bool
          False: not union. x,y are in same tree.
          True: do union. x,y are not in same tree.
    """
    global uf
    x, y = find(x), find(y)
    if x==y:
        return False
    else:
        if uf[x]<uf[y]:
            x, y = y, x
        uf[x] += uf[y]
        uf[y] = x
        return True
    
V, E = map(int, input().split())
edges = []
for _ in range(E):
    edges.append(tuple(map(int, input().split())))
    
uf = [-1]*V

# クラスカル法の部分
# Union-Findで閉路を作らないようにgreedyに辺を加えているだけ
mst = []
for e in sorted(edges, key=lambda x: x[2]):
    if find(e[0])!=find(e[1]):
        union(e[0], e[1])
        mst.append(e)
print(sum(map(lambda x: x[2], mst)))

Submission status: Accepted

Solution code:
v,e=map(int,input().split())
if e==0:print(0);exit()
class UnionFind:
    #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
    #method -> foo.hoge(huga)
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
edges=sorted([list(map(int,input().split())) for i in range(e)],key=lambda x:x[-1])
uf=UnionFind(v)
n,m,su=edges[0]
uf.unite(n,m)
for a,s,d in edges:
    if uf.same(a,s):continue
    uf.unite(a,s);su+=d
    if uf.size(n)==v:print(su);exit()

Submission status: Accepted

Solution code:
import heapq

def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
      heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

#########################
n,w = map(int,input().split())

edge = [[] for i in range(n)]
#隣接リスト edge[i]:[コスト,行先]
for i in range(w):
    x,y,z = map(int,input().split())
    #heapqを用いて、なるべく軽い辺から採用するため、zが先
    edge[x].append([z,y])
    edge[y].append([z,x])#無向のとき
print(prim_heap())

Submission status: Accepted

Solution code:
import heapq


class UnionFind:
    from collections import deque

    def __init__(self, v):
        self.v = v
        self._tree = list(range(v + 1))

    def _root(self, a):
        queue = self.deque()
        while self._tree[a] != a:
            queue.append(a)
            a = self._tree[a]
        while queue:
            index = queue.popleft()
            self._tree[index] = a
        return a

    def union(self, a, b):
        root_a = self._root(a)
        root_b = self._root(b)
        self._tree[root_b] = root_a

    def find(self, a, b):
        return self._root(a) == self._root(b)


V, E = map(int, input().split(' '))
heap = []
for _ in range(E):
    s, t, w = map(int, input().split(' '))
    heapq.heappush(heap, (w, s, t))

uf = UnionFind(V)
cost = 0
while heap:
    w, s, t = heapq.heappop(heap)
    if not uf.find(s, t):
        uf.union(s, t)
        cost += w

print(cost)