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):
class DisjointSet():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)

    def make_set(self, x):
        self.par[x] = x
        self.rank[x] = 0

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

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

class Edge():
    def __init__(self, source=0, target=0, cost=0):
        self.source = source
        self.target = target
        self.cost = cost

    def __lt__(self, e):
        return self.cost < e.cost

def kruskal(N, edges):
    
    total_cost = 0
    edges = sorted(edges)

    dset = DisjointSet(N)

    source, target = 0, 0
    for i in range(E):
        e = edges[i]
        if not dset.same_check(e.source, e.target):
            total_cost += e.cost
            dset.unite(e.source, e.target)
    return total_cost

V, E = list(map(int, input().split(' ')))
edges = []
for i in range(E):
    s, t, d = list(map(int, input().split(' ')))
    edges.append(Edge(s, t, d))
print(kruskal(V, edges))

Solution (Python):


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



import heapq
h = []
for i in range(e):
	s, t, w = map(int, input().split())
	heapq.heappush(h, (w, s, t))



p = [i for i in range(v)]
rank = [0 for i in range(v)]

def union(x, y):
 link(findSet(x), findSet(y))

def link(x, y):
 if rank[x] > rank[y]:
  p[y] = x
 else:
  p[x] = y
  if rank[x] == rank[y]:
   rank[y] = rank[y] + 1

def findSet(x):
 if x != p[x]:
  p[x] = findSet(p[x])
 return p[x]


def unite(x, y):
 union(x, y)

def same(x, y):
 x = findSet(x)
 y = findSet(y)
 if x == y:
  return True
 else :
  return False



s = 0
for i in range(e):
	edge = heapq.heappop(h)
	if same(edge[1], edge[2]) == False:
		s = s + edge[0]
		unite(edge[1], edge[2])


print(s)

Solution (Python):
import heapq

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

nv, ne = map(int, input().split())
nodes = [i for i in range(nv)]
q = []

for _ in range(ne):
  s, t, w = map(int, input().split())
  heapq.heappush(q, (w, s, t))

sum = 0

while q:
  w, s, t = heapq.heappop(q)
  root_s = find_root(s)
  root_t = find_root(t)
  if root_s != root_t:
    nodes[root_s] = root_t
    sum += w

print(sum)

Solution (Python):
v,e = map(int, input().split())
adj = [list(map(int, input().split())) for i in range(e)]
adj.sort(key = lambda x:x[2])
group = [[i] for i in range(v)]
key = [i for i in range(v)]
sum = 0
for i,j,k in adj:
    if key[i] != key[j]:
        h = key[j]
        group[key[i]] += group[h]
        sum += k
        for t in group[h]:
            key[t] = key[i]
        group[h] = []
        if len(group[key[i]]) == v:
            break
print(sum)

Solution (Python):
def root(x):
    if par[x] == x:
        return x
    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)
    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):
from sys import stdin
input = stdin.readline

from collections import defaultdict

MAX = 10000
infty = -1

class Disjoint():
    def __init__():
        return

def getRoot(x):
    global v
    for _ in range(v+1):
        if dic[x]["parent"] == x:
            return x
        x = dic[x]["parent"]

def unite(x, y):
    r = getRoot(x)
    l = getRoot(y)
    a = dic[r]["rank"]
    b = dic[l]["rank"]

    if a == b:
        dic[r]["rank"] += 1
        dic[l]["parent"] = r

    elif a > b:
        dic[l]["rank"] = 0
        dic[l]["parent"] = r

    elif a < b:
        dic[r]["rank"] = 0
        dic[r]["parent"] = l

lines = stdin.readlines()
dic = defaultdict()
v, e = map(int, lines[0].split())

E = [ list(map(int, lines[i+1].split())) for i in range(e)]
E = sorted(E, key=lambda x:x[2])


E = sorted(E, key=lambda x:x[2])

for _ in range(v):
    dic[_] = {"rank":0,"parent":_}

k = 0
total = 0

for edge in E:
    if getRoot(edge[0]) != getRoot(edge[1]):
        unite(edge[0], edge[1])
        k += 1
        total += edge[2]

print(total)

Solution (Python):
import heapq
v,e=map(int,input().split())
adj=[[] for _ in range(v)]
for _ in range(e):
  a,b,c=map(int,input().split())
  adj[a].append((b,c))
  adj[b].append((a,c))

visit=[0]*v
pq=[]
for next,w in adj[0]:
  heapq.heappush(pq,(w,next))
visit[0]=1
ans=0
while pq:
  w,next=heapq.heappop(pq)
  if visit[next]:
    continue
  visit[next]=1
  ans+=w
  for next,w in adj[next]:
    if not visit[next]:
      heapq.heappush(pq,(w,next))
print(ans)

Solution (Python):

def ifcycle(e1,e2):
    while uf[e1]>=0:
        e1=uf[e1]
    while uf[e2]>=0:
        e2=uf[e2]
    if e1==e2:
        return True
    if uf[e1]<=uf[e2]:
        uf[e1]+=uf[e2]
        uf[e2]=e1
    else:
        uf[e2]+=uf[e1]
        uf[e1]=e2
        return False
    
    
x,y=map(int,input().split())
a=[]

uf=[-1]*x
for i in range(y):
    v1,v2,v3=map(int,input().split())
    a.append([v3,v1,v2])
a.sort() 
ans=0 ; cnt=0
for p in range(y):
    w,s,t=a[p]
    if not ifcycle(s,t):
        ans+=w
        cnt+=1
        if cnt>=x: print(w)

print(ans)

Solution (Python):
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parent = [i for i in range(self.n)]
    self.rank = [0] * self.n
  
  def find_root(self, x):
    if self.parent[x] == x:
      return x
    else:
      self.parent[x] = self.find_root(self.parent[x])
      return self.parent[x]
  
  def unite(self, x, y):
    rx = self.find_root(x)
    ry = self.find_root(y)
    if rx == ry:
      return
    if self.rank[rx] < self.rank[ry]:
      self.parent[rx] = ry
    else:
      self.parent[ry] = rx
      if self.rank[rx] == self.rank[ry]:
        self.rank[rx] += 1
  
  def is_same(self, x, y):
    return self.find_root(x) == self.find_root(y)

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

uf = UnionFind(V)
total = 0
for e in edges:
  w, s, t = e
  if uf.is_same(s, t):
    continue
  uf.unite(s, t)
  total+= w
print(total)

Solution (Python):
import _heapq
inf=float("inf")


def prim():
    color=["white" for _ in range(v)]
    D=[inf for _ in range(v)]
    M=[[] for _ in range(v)]

    for s,t,w in STW:
        M[s].append([w,t])
        M[t].append([w,s])

    queue=[[0,0]]
    _heapq.heapify(queue)
    color[0]="gray"
    D[0]=0

    while len(queue)>0:
        num=_heapq.heappop(queue)[1]
        if color[num]=="black":continue
        color[num]="black"

        for i,j in M[num]:
            if i<D[j] and color[j]!="black":
                color[j]="gray"
                D[j]=i
                _heapq.heappush(queue,[i,j])

    return D


v,e=map(int,input().split())
STW=[list(map(int,input().split())) for _ in range(e)]
print(sum(prim()))

Solution (Python):
import sys

input = sys.stdin.readline


class UnionFind:
    """Union Find class.

    "Path compression" and "Union by rank" are used.

    References:
        <https://en.wikipedia.org/wiki/Disjoint-set_data_structure>
    """

    def __init__(self, N):
        self.N = N
        self.__make_set()

    def __make_set(self):
        self._parent = list(range(self.N))
        self._rank = [0] * self.N
        self._size = [1] * self.N

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

    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)

        if x_root == y_root:
            return

        x_rank = self._rank[x_root]
        y_rank = self._rank[y_root]
        if x_rank > y_rank:
            self._parent[y_root] = x_root
            self._size[x_root] += self._size[y_root]
        elif x_rank < y_rank:
            self._parent[x_root] = y_root
            self._size[y_root] += self._size[x_root]
        else:
            self._parent[y_root] = x_root
            self._rank[x_root] += 1
            self._size[x_root] += self._size[y_root]

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

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


def main():
    V, E = map(int, input().split())
    stw = [None] * E
    for i in range(E):
        stw[i] = tuple(map(int, input().split()))

    stw.sort(key=lambda x: x[2])
    uf = UnionFind(V)

    ans = 0
    for s, t, w in stw:
        if uf.same_set(s, t):
            continue
        uf.union(s, t)
        ans += w

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
class UnionFind:
    def __init__(self, num):
        self.parent = [i for i in range(num + 1)]

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

    def union(self, node1, node2):
        node1 = self.find(node1)
        node2 = self.find(node2)
        if node1 == node2:
            return
        if self.parent[node1] > self.parent[node2]:
            node1, node2 = node2, node1
        self.parent[node2] = node1
        return

    def same(self, node1, node2):
        return self.find(node1) == self.find(node2)



def kruskal(vertex_num, edges):
    ans = 0
    uf = UnionFind(vertex_num)
    
    edges.sort()
    for edge in edges:
        cost, frm, to = edge
        if uf.same(frm, to) is False:
            uf.union(frm, to)
            ans += cost
    return ans


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

print(kruskal(v, edges))

Solution (Python):



class UnionFind():
    def __init__(self, v):
        self.rank = [1] * v
        self.par = [x for x in range(v)]
    
    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):
        if self.find(x) == self.find(y):
            return False
        else:
            p_x = self.find(x)
            p_y = self.find(y)
            if self.rank[p_x] >= self.rank[p_y]:
                self.par[p_y] = p_x
                self.rank[p_y] += 1
            else:
                self.par[p_x] = p_y
                self.rank[p_x] += 1
    
    def same(self, x, y):
        p_x = self.find(x)
        p_y = self.find(y)
        return p_x == p_y
    
v, e = map(int, input().split())
e_l = [[int(x) for x in input().split()] for y in range(e)]
e_l.sort(key= lambda x: x[2])

def Kruskal(s):
    ans = 0
    uf = UnionFind(v)

    for _s, _t, _w in e_l:
        if not uf.same(_s, _t):
            uf.unite(_s, _t)
            ans += _w
    return ans
            
print(Kruskal(0))

Solution (Python):
from heapq import heappop, heappush
v_num, e_num = map(int, input().split())
pair_lst = [i for i in range(v_num)]
que = []
for _ in range(e_num):
  s, t, w = map(int, input().split())
  heappush(que, (w, s, t))
def find(x):
  if x == pair_lst[x]:
    return x
  else:
    tmp = find(pair_lst[x])
    pair_lst[x] = tmp
    return tmp

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

print(length_sum)

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


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

    def findset(self, A):
        if self.parent[A] < 0:
            return A
        self.parent[A] = self.findset(self.parent[A])
        return self.parent[A]

    def size(self, A):
        return -self.parent[self.findset(A)]

    def unite(self, A, B):
        A = self.findset(A)
        B = self.findset(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_same(self, A, B):
        return self.findset(A) == self.findset(B)
        

def kruskal(N):
    edges = sorted(E)
    ans = 0
    union = UnionFind(N)
    cnt = 0
    for w, s, t in edges:
        if cnt == N-1:
            break

        if union.is_same(s, t):
            continue
        else:
            union.unite(s, t)
            ans += w
            cnt += 1
            
    return ans

print(kruskal(v))

Solution (Python):


def kruskal():
    '''
    最小全域木のコストを求める
    '''
    cost = 0
    edge.sort()

    for c, u, v in edge:
        if same(u, v):
            continue
        union(u, v)
        cost += c

    return cost


def find(x):
    '''
    xの根を求める
    '''
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def union(x, y):
    '''
    xとyの属する集合を併合する
    '''
    x = find(x)
    y = find(y)
    
    if x == y:
        return False

    if par[x] > par[y]:
        x, y = y, x

    par[x] += par[y]
    par[y] = x
    return True


def same(x, y):
    '''
    xとyが同じ集合に属するかを判定する
    '''
    return find(x) == find(y)



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

par = [-1] * n  
edge = []       
for _ in range(w):
    x, y, z = map(int, input().split())
    edge.append([z, x, y])

print(kruskal())

Solution (Python):
class Graph:
    class Edge:
        def __init__(self, to, cost):
            """
            :param to:  終点ノード
            :param cost: 辺の重み
            """
            self.to, self.cost = to, cost

    def __init__(self, n, directed=False, decrement=True, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.edges = [[] for _ in range(self.n)]
        self.edges2 = []                            
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y, cost in edges:
            self.add_edge(x, y, cost)

    def add_edge(self, x, y, cost):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].append(self.Edge(y, cost))
        self.edges2.append((x, y, cost))
        if self.directed == False:
            self.edges[y].append(self.Edge(x, cost))
            self.edges2.append((y, x, cost))

    def prim(self):
        """
        :return: 最小全域木を選んだ時の重さの総和
        """
        start = 0  
        visit = [False] * self.n  
        next_set = [(0, start)]
        res = 0
        while next_set:
            dist, p = heappop(next_set)  
            if visit[p]:
                continue
            visit[p] = True
            res += dist  
            for edge in self.edges[p]:
                q, cost = edge.to, edge.cost
                if visit[q]:
                    continue
                heappush(next_set, (cost, q))  
        return res

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        if self.directed:
            G = nx.DiGraph()
        else:
            G = nx.Graph()
        for x in range(self.n):
            for edge in self.edges[x]:
                G.add_edge(x + self.decrement, edge.to + self.decrement, weight=edge.cost)


        edge_labels = {(i, j): w['weight'] for i, j, w in G.edges(data=True)}
        pos = nx.spring_layout(G)
        nx.draw_networkx(G, pos, with_labels=True)
        nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
        plt.axis("off")
        plt.show()


import sys
input = sys.stdin.readline
from heapq import *


N, M = map(int, input().split())
graph = Graph(N, directed=False, decrement=True)
for _ in range(M):
    x, y, cost = map(int, input().split())
    graph.add_edge(x, y, cost)

print(graph.prim())

Solution (Python):
class UnionFind:
  def __init__(self, n):
    self.parent = [i for i in range(n)]
    self.height = [0 for i in range(n)]
    
  def get_root(self, i):
    if self.parent[i] == i:
      return i
    else:
      self.parent[i] = self.get_root(self.parent[i])
      return self.parent[i]
    
  def unite(self, i, j):
    root_i = self.get_root(i)
    root_j = self.get_root(j)
    if root_i != root_j:
      if self.height[root_i] < self.height[root_j]:
        self.parent[root_i] = root_j
      else:
        self.parent[root_j] = root_i
        if self.height[root_i] == self.height[root_j]:
          self.height[root_i] += 1
          
  def is_in_group(self, i, j):
    if self.get_root(i) == self.get_root(j):
      return True
    else:
      return False
    
def kruskal(V, e_list):
  
  
  e_cost_sorted = []
  for e in e_list:
    e_cost_sorted.append([e[2], e[0], e[1]])
  e_cost_sorted.sort()
  uf_tree = UnionFind(V)
  cost = 0
  for k in range(len(e_cost_sorted)):
    c = e_cost_sorted[k][0]
    i = e_cost_sorted[k][1]
    j = e_cost_sorted[k][2]
    if not uf_tree.is_in_group(i, j):
      uf_tree.unite(i, j)
      cost += c
  print(cost)
  
V, E = map(int, input().split())
e_list = []
for i in range(E):
  e_list.append(list(map(int, input().split())))
kruskal(V, e_list)

Solution (Python):
class DisjointSet:
    def __init__(self,size):
        self.rank = [None]*size
        self.p = [None]*size
        for i in range(size):
            self.make_set(i)
        return
    
    def make_set(self,x):
        self.p[x] = x
        self.rank[x] = 0
        return
    
    def same(self,x,y):
        return self.find_set(x) == self.find_set(y)
        
    def unite(self,x,y):
        self.link(self.find_set(x),self.find_set(y))
        return
    
    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 find_set(self,x):
        if x != self.p[x]:
            self.p[x] = self.find_set(self.p[x])
        return self.p[x]
    
class Edge:
    def __init__(self,source,target,cost):
        self.source = source
        self.target = target
        self.cost = cost
        
def kruskal(edges):
    edges.sort(key=lambda x: x.cost)
    
    S = DisjointSet(n)
    K = []
    
    for i in range(m):
        if S.find_set(edges[i].source) != S.find_set(edges[i].target):
            K.append(edges[i])
            S.unite(edges[i].source,edges[i].target)
    return K

n,m = map(int,input().split())
edges = []

for i in range(m):
    s,t,w = map(int,input().split())
    edges.append(Edge(s,t,w))
    
K = kruskal(edges)

cost = 0
while K:
    edge = K.pop()
    cost += edge.cost
print(cost)

Solution (Python):
import heapq
def prim_heap():
    used = [True] * n 
    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)]

for i in range(w):
    x,y,z = map(int,input().split())
    edge[x].append([z,y])
    edge[y].append([z,x])
print(prim_heap())

Solution (Python):
class UnionFindTree():

    def __init__(self, n):
        
        self.n  = n
        
        self.root = [-1] * (n+1)
        
        self.rank = [1] * (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
        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 is_same(self,x,y):
        return self.find_root(x) == self.find_root(y)

    def count_node(self,x):
        return -1 * self.root[self.find_root(x)]
v, e = map(int, input().split())
edges = []
for _ in range(e):
    s, t, w = map(int, input().split())
    edges.append((w, s, t))


edges.sort()

def kuruskal(n, edges):
    uft = UnionFindTree(n)
    res = 0
    for e in edges:
        w, s, t = e
        if not uft.is_same(s, t):
            res += w
            uft.unite(s, t)
    return res

print(kuruskal(v, edges))

Solution (Python):
from heapq import heapify, heappop, heappush
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
G = []
for _ in [0]*M:
    a, b, c = map(int, input().split())
    heappush(G, (c, a, b))


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

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if x > y:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        self.u -= 1
        return True

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

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

    def num_union(self):
        return self.u


u = UnionFind(N)
ans = 0
while u.num_union() > 1:
    c, a, b = heappop(G)
    if u.same(a, b):
        continue
    u.unite(a, b)
    ans += c
print(ans)

Solution (Python):
from heapq import heappop, heappush

nv,ne=map(int,input().split())
pair_lst = [i for i in range(nv)]
que=[]
for i in range(ne):
    si,ti,wi=map(int,input().split())
    heappush(que,(wi,si,ti))

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

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

print(length_sum)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
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):
        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):
        return self.find(x) == self.find(y)


def main():
    V, E = map(int, readline().split())
    L = []
    for _ in range(E):
        s, t, w = map(int, readline().split())
        L.append([s, t, w])
    
    L.sort(key=lambda x: x[2])
    uf = UnionFind(V)
    ans = 0
    for i in range(E):
        s, t, w = L[i]
        if not uf.same(s, t):
            uf.union(s, t)
            ans += w
    print(ans)


if __name__ == '__main__':
    main()

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

Solution (Python):


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)

Solution (Python):
import heapq
def prim_heap(v):
    used = [True] * v 
    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))

Solution (Python):

class UnionFind():
    
    def __init__(self, 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:
            
            x = self.parent[x]
            children.append(x)

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

        return x

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

Solution (Python):

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)

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

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