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|  s 0  t 0  w 0  s 1  t 1  w 1 : 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.  s i and t i represent source and target verticess of i -th edge (undirected) and w i 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 ≤ w i ≤ 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

Solution (Python):
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()

Solution (Python):



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()

Solution (Python):
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)
    
    
    
    ans = 0
    for q in mst:
        ans += q.w

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
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', '')

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

    def get_root(self, 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:
            
            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
    
    while pri_queue:
        cost,to = heappop(pri_queue)
        if to not in spanning:
            
            ans += cost
            spanning.add(to)
            for cost,to in edge[to]:
                heappush(pri_queue,(cost,to))
    print(ans)
"""

Solution (Python):

V,E = map(int,input().split())
VWT = [list(map(int,input().split())) for i in range(E)]


class UF:
    def __init__(self,n):
        self.n = n
        self.root = [-1]*n 
        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) 
    
    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)

Solution (Python):








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

    def root(self, 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):
        
        
        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]  
        self.parent[B] = A  

        return True

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


Edges = []

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))

Solution (Python):




from operator import itemgetter

from sys import stdin,setrecursionlimit







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)

Solution (Python):
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)

Solution (Python):

import sys
input = lambda: sys.stdin.buffer.readline()[:-1].decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

class UnionFind:
    __slots__ = ['id','sz']

    def __init__(self, n):
        self.id = [-1] * n
        self.sz = n

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

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

    def union(self, x, y):
        s1, s2 = self.root(x), self.root(y)
        if s1 != s2:
            if self.id[s1] <= self.id[s2]:
                self.id[s1] += self.id[s2]
                self.id[s2] = s1
            else:
                self.id[s2] += self.id[s1]
                self.id[s1] = s2
            self.sz-=1
            return True
        return False


V,E=map(int,input().split())
uf=UnionFind(V)
ans=0
stw=[list(map(int,input().split())) for i in range(E)]
stw.sort(key=lambda tup:tup[2])
for s,t,w in stw:
    if not uf.find(s,t):
        uf.union(s,t)
        ans+=w
print(ans)

Solution (Python):

import sys

sys.setrecursionlimit(100000)



def find(x, S):
    if S[x] == x:
        return x
    else:
        S[x] = find(S[x], S)
        return S[x]



def same(x, y, S):
    return find(x, S) == find(y, S)



def unite(x, y, S):
    rx = find(x, S)
    ry = find(y, S)
    if rx == ry:
        return None
    else:
        S[rx] = ry

if __name__ == '__main__':
    [V, E] = [int(i) for i in input().split()]

    S = [i for i in range(V)]
    edges = []

    ans = 0

    for i in range(E):
        edges.append([int(i) for i in input().split()])

    for s, t, w in sorted(edges, key=lambda x: x[2]):
        if same(s, t, S):
            continue
        else:
            unite(s, t, S)
            ans += w


    print(ans)

Solution (Python):
par  =[]
V, E = [int(s) for s in input().split()]
for i in range(V+1):
    par.append(i)

graph = []

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

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

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

def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        par[x] = y

graph = sorted(graph, key=lambda x: x[2])
ans = 0
for g in graph:
    if not same(g[0], g[1]):
        union(g[0], g[1])
        ans += g[2]
print(ans)

Solution (Python):
import sys
import collections
sys.setrecursionlimit(10**7)


def init(n):
    return list(range(n+1))

def find(lis, x):
    if lis[x] == x:
        return x
    else:
        lis[x] = find(lis, lis[x])
        return lis[x]

def sameset(lis, x, y):
    return find(lis, x) == find(lis, y)

def union(lis, x, y):
    x = find(lis, x)
    y = find(lis, y)
    if x != y:
        lis[x] = y

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

cost = 0
for (s,t,w) in sorted(graph, key=lambda x: x[2]):
    if not sameset(union_find_tree,s,t):
        union(union_find_tree,s,t)
        cost += w
print(cost)

Solution (Python):
from typing import List

class UnionFind:
	def __init__(self, V: int) -> None:
		self.V: int = V
		self.pi: List[int] = [i for i in range(V)]
		self.rank: List[int] = [0 for _ in range(V)]

	def findSet(self, x: int) -> int:
		if x != self.pi[x]:
			self.pi[x] = self.findSet(self.pi[x])
		return self.pi[x]

	def same(self, x: int, y: int) -> bool:
		return self.findSet(x) == self.findSet(y)

	def link(self, x: int, y: int) -> None:
		if self.rank[x] > self.rank[y]:
			self.pi[y] = x
		else:
			self.pi[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def unite(self, x: int, y: int) -> None:
		self.link(self.findSet(x), self.findSet(y))


class Edge:
	def __init__(self, source: int, target: int, cost: int) -> None:
		self.source = source
		self.target = target
		self.cost = cost


def kruskal(n: int, edges: List[Edge]) -> int:
	totalCost: int = 0
	edges.sort(key=lambda e: e.cost)
	uf: UnionFind = UnionFind(n + 1)
	for e in edges:
		if not uf.same(e.source, e.target):
			totalCost += e.cost
			uf.unite(e.source, e.target)
	return totalCost


if __name__ == "__main__":
	n, m = map(int, input().split())
	edges: List[Edge] = []
	for _ in range(m):
		s, t, c = map(int, input().split())
		edges.append(Edge(s, t, c))
	ans = kruskal(n, edges)
	print(ans)

Solution (Python):

class UnionFind:  
    def __init__(self, size):  
        self.parent = [i for i in range(size)]
        self.rank = [0] * (size)
        self.size = size

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

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

    def unite(self, x, y):  
        x, y = self.find(x), self.find(y)
        if x == y:  
            return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def kruskal() -> int:
    total_cost, undetermined, uf = 0, N, UnionFind(N)
    for cost, v, u in E:
        if not uf.is_same(v, u):
            uf.unite(v, u)
            total_cost += cost
            undetermined -= 1
        if not undetermined:
            break
    return total_cost


def main():
    global N, E
    N, M, *E = map(int, open(0).read().split())
    E = [(c, v, u) for (v, u, c) in zip(*[iter(E)] * 3)]
    E.sort()
    ans = kruskal()
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

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

Edg = []

for _ in range(e):
    s,t,w = map(int, input().split( ))
    Edg.append([w,s,t])
    Edg.append([w,t,s])
    
Edg.sort(reverse = True)

UF = [i for i in range(v)]

ans = 0


for i in range(2*e):
    edg = Edg.pop()
    s, t = edg[1],edg[2]
    Ls = [s]
    Lt = [t]
    root_s = UF[s]
    
    while root_s!=s:
        Ls.append(root_s)
        s = root_s
        root_s = UF[root_s]
        
    root_t = UF[t]
    while root_t!=t:
        Lt.append(root_t)
        t = root_t
        root_t = UF[root_t]
    
    if root_s == root_t:
        continue
    
    else:
        
        for j in Lt:
            UF[j] = root_s
        
        ans += edg[0]
        
    


print(ans)

Solution (Python):
"""
クラスカルのアルゴリズム
"""

class UnionFindTree:
  def __init__(self, n: int):
    self.__parent = [i for i in range(n)]
    self.__rank = [0 for i in range(n)]

  def unite(self, x, y) -> None:
    self.__link(self.__find_set(x), self.__find_set(y))

  def same(self, x, y) -> bool:
    return self.__find_set(x) == self.__find_set(y)

  def __find_set(self, x):
    if x != self.__parent[x]:
      self.__parent[x] = self.__find_set(self.__parent[x])
    return self.__parent[x]

  def __link(self, x, y):
    if self.__rank[x] < self.__rank[y]:
      self.__parent[x] = y
    else:
      if self.__rank[x] == self.__rank[y]:
        self.__rank[x] += 1
      self.__parent[y] = x


class Edge:
  def __init__(self, src, dst, weight):
    self.src = src
    self.dst = dst
    self.weight = weight


V, E = map(int, input().split())
INF = 10**10
edges = [Edge(*map(int, input().split())) for i in range(E)]
edges.sort(key=lambda e: e.weight)
total_cost = 0
t = UnionFindTree(V)

for e in edges:
  if not t.same(e.src, e.dst):
    t.unite(e.src, e.dst)
    total_cost += e.weight

print(total_cost)

Solution (Python):
import sys
input = sys.stdin.readline

def same_tree(node_a, node_b):
    if node_a.root() == node_b.root():
        return True

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

def main():
    V, E = map(int, input().split())

    nodes = [Node() for i in range(V)]

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

    ans = 0
    for i in range(E):
        s, t, w = stw[i]
        if not same_tree(nodes[s], nodes[t]):
            unite(nodes[s], nodes[t])
            ans += w
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
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)

Solution (Python):
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rank = [0]*(n+1)

	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 0
		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 isSame(self, x, y):
		return self.find(x) == self.find(y)

V,E,*t = map(int,open(0).read().split())
edges = sorted([(w,s,t) for s,t,w in zip(*[iter(t)]*3)])
uf = UnionFind(V)
ans = 0
for w,s,t in edges:
	if not uf.isSame(s,t):
		ans += w
		uf.unite(s,t)
print(ans)

Solution (Python):
from heapq import heappop, heappush
from typing import List, Tuple


def find(x):
    global parents
    if x == parents[x]:
        return x
    else:
        tmp = find(parents[x])
        parents[x] = tmp
        return tmp


if __name__ == "__main__":
    V, E = map(int, input().split())
    parents = [i for i in range(V)]
    que: List[Tuple[int, int , int]] = []
    for _ in range(E):
        s, t, w = map(int, input().split())
        heappush(que, (w, s, t))

    ans = 0
    while que:
        w, s, t = heappop(que)
        root_s = find(s)
        root_t = find(t)
        if root_s != root_t:
            parents[root_s] = root_t
            ans += w

    print(ans)

Solution (Python):
from collections import defaultdict
from heapq import heappush, heappop

v, e = map(int, input().split())
E = defaultdict(list)
for _ in range(e):
    s, t, w = map(int, input().split())
    E[s].append((w, t))
    E[t].append((w, s))
d = [float("inf")] * v
used = [False] * v
d[0] = 0


ans = 0
q = []
heappush(q, (0, 0))
while q:
    dist, now = heappop(q)
    if used[now]:
        continue
    used[now] = True
    ans += dist
    for w, nxt in E[now]:
        if not used[nxt]:
            heappush(q, (w, nxt))
print(ans)

Solution (Python):

class Kruskal_UnionFind():
    
    def __init__(self, N):
        self.edges = []
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

    def add(self, u, v, d):
        """
        u = from, v = to, d = cost
        """
        self.edges.append([u, v, d])

    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:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        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 size(self, x):
        x = self.find(x)
        return self.counter[x]

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

    def Kruskal(self):
        """
        return: 最小全域木のコストの和
        """
        edges = sorted(self.edges, key=lambda x: x[2])  
        res = 0
        for e in edges:
            if not self.same(e[0], e[1]):
                self.unite(e[0], e[1])
                res += e[2]
        return res

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

Krus = Kruskal_UnionFind(V)

for _ in range(E):
    s, t, w = map(int, input().split())
    Krus.add(s, t, w)

ans = Krus.Kruskal()

print(ans)

Solution (Python):
class DisjointSet:
    def __init__(self, size):
        self.rank = [0 for i in range(size)]
        self.p = [0 for i in range(size)]
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 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 kruskal(V, e):
    
    e = sorted(e, key=lambda x: x[2])
    S = DisjointSet(V)
    K = []
    for s, t, w in e:
        
        if not S.same(s, t):
            S.unite(s, t)
            K.append((s, t, w))
    return K

if __name__ == '__main__':
    V, E = map(int, input().split())
    
    e = [tuple(map(int, input().split())) for i in range(E)]
    K = kruskal(V, e)
    ans = 0
    for s, t, w in K:
        ans += w
    print(ans)

Solution (Python):


from heapq import heappop,heappush

n,m=map(int,input().split())
edge=[[] for _ in range(n)]
for i in range(m):
    u,v,c=map(int,input().split())
    edge[u].append((c,v))
    edge[v].append((c,u))


def prim(s):
    d=[float('inf')]*n
    visited=[False]*n
    d[s]=0
    visited[s]=True
    que=[]
    for e in edge[s]:
        heappush(que,e)
    while que:
        c,v=heappop(que)
        if visited[v]:continue
        d[v]=c
        visited[v]=True
        for cost,vtx in edge[v]:
            if visited[vtx]:continue
            hq=(cost,vtx)
            heappush(que,hq)
    return d


print(sum(prim(0)))

Solution (Python):
def root(r):
    if par[r] == r:
        return r
    par[r] = root(par[r])
    return par[r]
 
def same(x, y):
    return root(x) == root(y)
 
def unite(x, y):
    x = root(x)
    y = root(y)
    par[x] = y
 
 
 
v,e = map(int, input().split())
adj = [list(map(int, input().split())) for i in range(e)]
adj.sort(key = lambda x:x[2])
par = [i for i in range(v)]
sum = 0
 
for i,j,k in adj:
    if not same(i, j):
        sum += k
        unite(i, j)
print(sum)

Solution (Python):
import array
import collections
import heapq
 
 
AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
MAX_INT = 2147483647
NO_V = -1
 
 
def compute_mst_prim(v, adj_list):
    pred = collections.defaultdict(lambda: NO_V)
    key = collections.defaultdict(lambda: MAX_INT)
    key[0] = 0
    pq = [(key[i], i) for i in range(v)]
    heapq.heapify(pq)
    in_pq = array.array("B", (True for tmp in range(v)))
    while pq:
        tmp, u = heapq.heappop(pq)
        in_pq[u] = False
        for i, cost in adj_list[u]:
            if in_pq[i]:
                weight = cost
                if weight < key[i]:
                    pred[i] = u
                    key[i] = weight
                    heapq.heappush(pq, (weight, i))
                    in_pq[i] = True
    return pred, key
 
 
if __name__ == '__main__':
    v, e = map(int, input().split())
    a_list = collections.defaultdict(set)
    for _ in range(e):
        s, t, w = map(int, input().split())
        a_list[s].add(AdjacentVertex(t, w))
        a_list[t].add(AdjacentVertex(s, w))
    tmp , key = compute_mst_prim(v, a_list)
    print(sum(key.values()))