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:

n, m = map(int, input().split())
stw = [list(map(int, input().split())) for _ in range(m)]
stw = sorted(stw, key=lambda x:x[2])

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())

def kruskal():
  res = 0 
  uf = UnionFind(n)
  for i in range(m):
    s, t, w = stw[i]
    if not uf.isSameGroup(s, t):
      uf.Unite(s, t)
      res += w 
  
  return res

print(kruskal())

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/problems/GRL_2_A
# 最小全域木

# https://qiita.com/Kerzival/items/6923c2eb3b91be86f19f
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

# 入力値の取得・構造化
V, E = map(int, input().split())
edges = []

for i in range(E):
    s, t, w = map(int, input().split())
    edges.append({"s": s, "t": t, "w": w})

# kruskal
edges = sorted(edges, key=lambda x:x['w'])
union_find = UnionFind(V)
res = 0
for i in range(E):
    edge = edges[i]
    if not union_find.isSameGroup(edge["s"], edge["t"]):
        union_find.Unite(edge["s"], edge["t"])
        res = res + edge["w"]
print(f"{res}")

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

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

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n,m = LI()
    v = []
    for i in range(m):
        a,b,c = LI()
        v.append((c,a,b))
    v.sort()
    par = [i for i in range(n)]
    rank = [0]*n
    ans = 0
    for c,x,y in v:
        if root(x) != root(y):
            ans += c
            unite(x,y)
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()


def minimum_spanning_tree(n, info):
    """
    頂点の数:nと辺の情報i:infoから最小全域木([[辺の始点の頂点,辺の終点の頂点, 重み], ...])を返す。
    info:[[辺の始点の頂点,辺の終点の頂点, 重み], ...](bellman_ford()の入力形式)
    """
    ans = []
    info.sort(key=itemgetter(2))

    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):
            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):
            return -self.parents[self.find(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 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())

    uf = UnionFind(n)
    for i in info:
        if not uf.same(i[0], i[1]):
            ans.append(i)
            uf.union(i[0], i[1])
    return ans


V, E = map(int, input().split())
stw = [list(map(int, input().split())) for _ in range(E)]
print(sum([i[2] for i in minimum_spanning_tree(V, stw)]))

Submission status: Accepted

Solution code:
V, E = map(int, input().split())

PAR = list(range(V))
 
def root(x):
    if PAR[x] == x:
        return x
    else:
        PAR[x] = root(PAR[x])
        return PAR[x]
 
def same(x, y):
    return root(x) == root(y)
 
def unite(x, y):
    x = root(x)
    y = root(y)
    
    if x == y:
        return
    
    PAR[max(x, y)] = min(x, y)


class Edge:
    def __init__(self, u, v, cost):
        self.u = u
        self.v = v
        self.cost = cost
        
        

EDGES = []
for _ in range(E):
    s, t, w = map(int, input().split())
    EDGES.append(Edge(s, t, w))
    
def kruskal():
    edges = sorted(EDGES, key=lambda a: a.cost )
    res = 0
    for edge in edges:
        if (not same(edge.u, edge.v)):
            unite(edge.u, edge.v)
            res += edge.cost
    
    return res
    
print(kruskal())

Submission status: Accepted

Solution code:
import heapq

def prim():
    used = [1] * n
    used[0] = 0
    lis = []
    res = 0
    
    for q in edge[0]:
        heapq.heappush(lis,q)
        
    while lis:
        minedge = heapq.heappop(lis)
        
        if used[minedge[1]] == 0:
            continue

        v = minedge[1]
        used[v] = 0

        for q in edge[v]:
            if used[q[1]] == 1:
                heapq.heappush(lis , q )
        res += minedge[0]
    return res
    
n , m = map(int,input().split())
edge = [[] for _ in range(n)]

for _ in range(m):
    ad ,b ,c = map(int,input().split())
    edge[ad].append([c , b])
    edge[b].append([c , ad])
print(prim())

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)


V, E = map(int, input().split())
uft = UnionFind(V)
l = [tuple(map(int, input().split())) for _ in range(E)]
l.sort(key=lambda x:x[2])

ans = 0
for s, t, w in l:
    s += 1; t += 1
    if not uft.isunited(s, t):
        ans += w
        uft.unite(s, t)

print(ans)

Submission status: Accepted

Solution code:
import heapq

num_V, num_E = map(int, input().split())
E = [[] for _ in range(num_V)]
for _ in range(num_E):
	ts,tt,tw = map(int, input().split())
	E[ts].append([tt,tw])
	E[tt].append([ts,tw])

flg = [0] * num_V
ans = []
q = []
heapq.heappush(q,[0,0])

while q:
	cd, cp = heapq.heappop(q)
	if flg[cp] == 0:
		flg[cp] = 1
		ans.append(cd)
	else:
		continue

	for np, nd in E[cp]:
		if flg[np] == 0:
			heapq.heappush(q,[nd, np])

print(sum(ans))

Submission status: Accepted

Solution code:
import math,itertools,bisect,sys,copy,queue

def LI(): return [int(x) for x in sys.stdin.readline().split()]

V,E = LI()
q = queue.PriorityQueue()
for _ in range(E):
    s,t,w = LI()
    q.put((w,s,t))

g = [i for i in range(V)]
root = [[i] for i in range(V)]

ans = 0
while not q.empty():
    w, s, t = q.get()
    if g[s] == g[t]: continue
    ans += w
    if len(root[g[s]]) < len(root[g[t]]):
        s ,t = t, s
    g_t = g[t]
    for i in root[g_t]:
        g[i] = g[s]
    root[g[s]].extend(root[g_t])
    root[g_t] = []

print (ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop, heapify

V, E = map(int, sys.stdin.readline().strip().split())

graph = [[] for _ in range(V)]
for _ in range(E):
	s, t, w = map(int, sys.stdin.readline().strip().split())
	graph[s].append((w, t))
	graph[t].append((w, s))
	
used = set()
q = []
for i in range(V):
    if len(graph[i]):
        for w, t in graph[i]:
            q.append((w, t))
        used.add(i)
        break
heapify(q)

ans = 0
while q:
    w, s = heappop(q)
    if s in used:
        continue
    used.add(s)
    ans += w
    for w, t in graph[s]:
        if t in used:
            continue
        heappush(q, (w, t))

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

INF = 10 ** 20

v_num, e_num= map(int, input().split())
edges_lst = [[] for _ in range(v_num)]
dist_lst = [INF for _ in range(v_num)]

min_dis = INF
for _ in range(e_num):
    s, t, dist = map(int, input().split())
    edges_lst[s].append((dist, t))
    edges_lst[t].append((dist, s))
    if min_dis > dist:
        min_dis = dist
        node1,node2 = s,t
    
if v_num==1:
    print(0)
else:
    que = []
    for v in edges_lst[node1]:
        heappush(que, v)
    for v in edges_lst[node2]:
        heappush(que, v)
        S = {node1,node2}
        ans = min_dis


    while len(S)!=v_num:
        dist, node = heappop(que)
        if node not in S:
            S.add(node)
            ans += dist
            for dist2 ,v in edges_lst[node]: 
                if v not in S:
                    heappush(que, (dist2, v))

    print(ans)

Submission status: Accepted

Solution code:
import heapq

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

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

class UnionFind:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N # 最初はそれぞれのノードが誰ともUnionをつくってないから木の深さが０
        self.count = 0 # unite回数
    
    # 根を返す
    def root(self, a):
        if self.parent[a] == a:
            return a
        else:
            # 親を見に行く
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    
    # 同じUnionに属するかどうか
    def is_same(self, a, b):
        return self.root(a) == self.root(b)
    
    # 同じUnionにする
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return 
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]:
                self.rank[ra] += 1
        self.count += 1

uf = UnionFind(V)
total = 0
while q:
    w,s,t = heapq.heappop(q)
    if not uf.is_same(s,t):
        uf.unite(s,t)
        total += w

print(total)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush,heapify

class Graph():
    def __init__(self,n,edge,directed=False):
        self.n = n
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0]].append((e[1],e[2]))
            if not directed:
                self.graph[e[1]].append((e[0],e[2]))
                
    def prim(self):
        used = [False for _ in range(self.n)]
        used[0] = True
        heap = [(cost,adj) for adj,cost in self.graph[0]]
        heapify(heap)
        res = 0
        while heap:
            cost,node = heappop(heap)
            if used[node]:
                continue
            used[node] = True
            res += cost
            for adj,adjcost in self.graph[node]:
                if used[adj]:
                    continue
                heappush(heap,(adjcost,adj))
        return res
        
import sys
input = sys.stdin.readline

V,E = map(int,input().split())
edge = [tuple(map(int,input().split())) for _ in range(E)]

g = Graph(V,edge)

print(g.prim())

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


def kruskal(edges, v):
    nums = [i for i in range(v)]
    rank = [0 for i in range(v)]

    def find_top(x):
        if (nums[x] != x):
            nums[x] = find_top(nums[x])
        return nums[x]

    def unite(x, y):
        x = find_top(x)
        y = find_top(y)
        if rank[x] > rank[y]:
            nums[y] = x
        else:
            nums[x] = y
            if (rank[x] == rank[y]):
                rank[y] += 1

    def same(x, y):
        return find_top(x) == find_top(y)
    weight = 0
    while len(edges) > 0:
        w, s, t = heappop(edges)
        if not same(s, t):
            unite(s, t)
            weight += w
    return weight


def main():
    v, e = map(int, input().split())
    edges = []
    for _ in range(e):
        s, t, w = map(int, input().split())
        heappush(edges, (w, s, t))
    print(kruskal(edges, v))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

INF = 2000000000



class Node:
    def __init__(self, num):
        self.num = num
        self.parent = self
        self.rank = 0
    
def findSet(node):
    tmp = []
    while node.parent != node:
        tmp.append(node)
        node = node.parent
    
    while tmp:
        tmp.pop().parent = node
    return node

def unite(x, y):
    node1 = findSet(nodes[x])
    node2 = findSet(nodes[y])
    if node1.rank == node2.rank:
        node2.parent = node1
        node1.rank += 1
    elif node1.rank > node2.rank:
        node2.parent = node1
    else:
        node1.parent = node2

def same(x, y):
    node1 = findSet(nodes[x])
    node2 = findSet(nodes[y])
    return node1.parent == node2.parent





class Edge:
    def __init__(self, source, target, cost):
        self.source = source
        self.target = target
        self.cost = cost
    
def kruskal():
    edges.sort(key = lambda u:u.cost)
    
    for i in range(e):
        if findSet(edges[i].source) != findSet(edges[i].target):
            unite(edges[i].source.num, edges[i].target.num)
            K.append(edges[i])
    
    total = 0
    for tmp in K:
        total += tmp.cost
    print(total)


nums=list(map(int,input().split()))
n = nums[0]
e = nums[1]

edges = []
nodes = []
for i in range(n):
    nodes.append(Node(i))

for i in range(e):
    nums=list(map(int,input().split()))
    tmp = Edge(nodes[nums[0]], nodes[nums[1]], nums[2])
    edges.append(tmp)




K = []

kruskal()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
G = []
E = []

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

	def make(self, n):
		for i in range(n):
			self.parent[i] = i

	def unite(self, x, y):
		xroot = self.findset(x)
		yroot = self.findset(y)
		if self.rank[xroot] < self.rank[yroot]:
			self.parent[xroot] = yroot
		elif self.rank[xroot] > self.rank[yroot]:
			self.parent[yroot] = xroot
		else:
			self.parent[xroot] = yroot
			self.rank[yroot] += 1
			node = y
			while True:
				self.rank[node] += 1
				if self.parent[node] == node:
					break
				node = self.parent[node]
			self.rank[y] += 1

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

class Edge:
    def __init__(self, fr, to, w):
        self.fr = fr
        self.to = to
        self.w = w

def kruskal(v, e):
    global E
    E.sort(key=lambda x: x.w)
    uf = UnionFind(v)
    mst = []
    for i in range(e):
        if uf.findset(E[i].fr) != uf.findset(E[i].to):
            uf.unite(E[i].fr, E[i].to)
            mst.append(E[i])
    return mst


def main():
    global G, E
    n, e = map(int, input().strip().split())
    G = [[] for _ in range(n)]
    E = [0] * e
    for i in range(e):
        s, t, w = map(int, input().strip().split())
        E[i] = Edge(s, t, w)
    mst = kruskal(n, e)
    # print(mst)
    # from functools import reduce
    # print(reduce(lambda x, y: x.w + y.w, mst))
    ans = 0
    for q in mst:
        ans += q.w

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

v,e = map(int,input().split())
ans = 0
par = [i for i in range(v)]
rank = [0]*v
def find(x,par):
    if par[x] == x:
        return par[x]
    else:
        return find(par[x],par)
def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

L = []
for i in range(e):
    a,b,d = map(int,input().split())
    L.append([d,a,b])
L.sort()
for i in range(e):
    cur = heapq.heappop(L)
    if find(cur[1],par) != find(cur[2],par):
        ans += cur[0]
        unite(cur[1],cur[2],par,rank)
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

V, E = MAP()
stw = [LIST() for _ in range(E)]

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n))
        self.ranks = [0 for _ in range(n)]
 
    def get_root(self, x):
        if self.parents[x] == x:
            return x
        self.parents[x] = self.get_root(self.parents[x])
        return self.parents[x]
 
    def merge(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)
        if x != y:
            if self.ranks[x] < self.ranks[y]:
                self.parents[x] = y
            else:
                self.parents[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1
 
def kruskal(n_nodes, edges):
    edges.sort(key=itemgetter(2))
    res = []
    uf = UnionFind(n_nodes)
    for e in edges:
        if uf.get_root(e[0]) != uf.get_root(e[1]):
            res.append(e)
            uf.merge(e[0], e[1])
    return res

edges = []
for s, t, w in stw:
	edges.append((s, t, w))

tree = kruskal(V, edges)
ans = sum(x[2] for x in tree)
print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop, heapify
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# UnionFind
class UnionFind():
    def __init__(self, n):
        self.nodes=[-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x]=self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root

def main():
    N,M = MI()
    uf=UnionFind(N)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes

    edge = []
    for i in range(M):
        s,t,c = MI()
        edge.append((c,s,t))


    edge.sort()

    ans = 0
    for cost,u,v in edge:
        if get_root(u)!=get_root(v):
            unite(u,v)
            ans += cost

    print(ans)
if __name__ == '__main__':
    main()
"""
 N,M = MI()
    edge = [[] for _ in range(N)]
    for i in range(M):
        s,t,c = MI()
        edge[s].append((c,t))
        edge[t].append((c,s))
    pri_queue = edge[0]
    heapify(pri_queue)
    spanning = set([0])
    ans = 0
    # print(pri_queue)
    while pri_queue:
        cost,to = heappop(pri_queue)
        if to not in spanning:
            # print(to)
            ans += cost
            spanning.add(to)
            for cost,to in edge[to]:
                heappush(pri_queue,(cost,to))
    print(ans)
"""

Submission status: Accepted

Solution code:
#A
V,E = map(int,input().split())
VWT = [list(map(int,input().split())) for i in range(E)]

#UnionFind
class UF:
    def __init__(self,n):
        self.n = n
        self.root = [-1]*n #root[x]<0 ならxが根かつその値が木の要素数
        self.rank = [0]*n #木の深さ
    def __del__(self):
        pass
        
    def find(self,x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
            
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x]+=1
                
    def same(self,x,y):
        return self.find(x) == self.find(y) #bool
    
    def count(self,x):
        return -self.root[self.find(x)]

uf = UF(V)
    
VWT = sorted(VWT, key=lambda x:x[2])
ans = 0
for vwt in VWT:
    v,w,t = vwt
    if not uf.same(v,w):
        uf.unite(v,w)
        ans+=t
        
print(ans)

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_2_A
# 最小全域木、またお前か(プリムのアルゴリズムでできるやつ)
# ここではクラスカルのアルゴリズムを用いて解く。
# アイデアとしては辺の重みの小さい順にgreedyにノード同士をつないでいけば、必ず最小全域木になるでしょうというもの
# ただし木とならないような辺は省かなければ行けない。
# 辺を追加する際に木であることを崩さないように効率よく判定するのにunion-find木を使っている


class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        # 親ノードをしめす。負は自身が親ということ。
        self.parent = [-1] * N  # idxが各ノードに対応。
        # 本で言うrankはこの実装では扱っていない。

    def root(self, A):  # 本で言うfindset
        # print(A)
        # ノード番号を受け取って一番上の親ノードの番号を帰す
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])  # 経由したノードすべての親を上書き
        return self.parent[A]

    def size(self, A):
        # ノード番号を受け取って、そのノードが含まれている集合のサイズを返す。
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        # ノード番号を2つ受け取って、そのノード同士をつなげる処理を行う。
        # 引数のノードを直接つなぐ代わりに、親同士を連結する処理にする。
        A = self.root(A)
        B = self.root(B)

        # すでにくっついている場合
        if (A == B):
            return False

        # 大きい方に小さい方をくっつけたほうが処理が軽いので大小比較
        if (self.size(A) < self.size(B)):
            A, B = B, A

        # くっつける
        self.parent[A] += self.parent[B]  # sizeの更新
        self.parent[B] = A  # self.rootが呼び出されればBにくっついてるノードもすべて親がAだと上書きされる

        return True

    def is_in_same(self, A, B):
        return self.root(A) == self.root(B)


Edges = []
# load data
n_V, n_E = list(map(int, input().split()))
for _ in range(n_E):
    s, t, w = list(map(int, input().split()))
    Edges.append((w, s, t))


def kruskal(N, Edges):
    '''
    Nは頂点数、Ndgesは各要素が(w,s,t)を前提としたlist
    '''
    edges = sorted(Edges)
    ret = 0
    union = UnionFind(N)
    n_edges = 0
    for w, s, t in edges:
        if n_edges == N - 1:
            # 全域木になったら早期終了可
            break
        if union.is_in_same(s, t):
            continue
        union.unite(s, t)
        ret += w
        n_edges += 1
    return ret


print(kruskal(n_V, Edges))

Submission status: Accepted

Solution code:
#import pysnooper
#import numpy
#import os,re,sys,operator
#from collections import Counter,deque
from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from bisect import bisect_left
#from copy import deepcopy
#import heapq
#import math
#import string
#from time import time

setrecursionlimit(10**6)
input=stdin.readline

class Union_find:
    
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rank=[0]*(n+1)
    
    def find_root(self,x):
    
        if self.root[x]<0: return x
        else:
            self.root[x]=self.find_root(self.root[x])
            return self.root[x]
    
    def unite(self,x,y):
    
        x,y=self.find_root(x),self.find_root(y)
    
        if x==y: return 
        elif self.rank[x]>self.rank[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]: self.rank[y]+=1
    
    def same(self,x,y):
        return self.find_root(x)==self.find_root(y)
    
    def count(self,x):
        return -self.root[self.find_root(x)]

v,e=map(int,input().split())
graph=Union_find(v)

a=sorted([list(map(int,input().split())) for _ in range(e)],key=itemgetter(2))
ans=0
for i in a:
    s,t,w=i
    if not graph.same(s,t):
        graph.unite(s,t)
        ans+=w
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    MAX_N = 0
    PAR  = [] 
    RANK = []

    def __init__(self,n):
        self.MAX_N = n
        self.PAR = [ i for i in range(n)]
        self.RANK= [ 0 ] * n

    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 unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.RANK[x] < self.RANK[y]:
            self.PAR[x] = y
        else:
            self.PAR[y] = x
            if self.RANK[x] == self.RANK[y]:
                self.RANK[x] += 1

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

def kruskal(Edge):
    Edge.sort(key=lambda x:x[2])
    data = UnionFind(V)
    res = 0
    for i in range(E):
        u = Edge[i][0]
        v = Edge[i][1]
        d = Edge[i][2]
        if data.same(u,v) == False:
            data.unite(u,v)
            res += d
    return res

V,E = map(int,input().split())
Edge = []
for _ in range(E):
    Edge.append(list(map(int,input().split())))

ans = kruskal(Edge)
print(ans)