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:
#!/usr/bin/env python3
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)

Submission status: Accepted

Solution code:
# from typing import List
import sys

sys.setrecursionlimit(100000)

# 木の根を返す
# def find(x: int, S: List[int]) -> int:
def find(x, S):
    if S[x] == x:
        return x
    else:
        S[x] = find(S[x], S)
        return S[x]

# xとyが同じ集合に属すかの判定
# def same(x: int, y: int, S: List[int]) -> bool:
def same(x, y, S):
    return find(x, S) == find(y, S)

# xとyの属する集合を結合
# def unite(x: int, y: int, S: List[int]) -> None:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# GRL_2_A - Minimum Spanning Tree
class UnionFind:  # O(α(N))
    def __init__(self, size):  # construct a Union-Find tree (1-idx)
        self.parent = [i for i in range(size)]
        self.rank = [0] * (size)
        self.size = size

    def find(self, x):  # find the group (root) of a vertex
        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):  # check two vertices are in the same group
        return self.find(x) == self.find(y)

    def unite(self, x, y):  # unite two groups
        x, y = self.find(x), self.find(y)
        if x == y:  # the same group
            return
        # unite a smaller one to a bigger one in order to balance trees
        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()

Submission status: Accepted

Solution code:
#import heapq
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
#cnt = v

for i in range(2*e):#無向辺で2倍
    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:
        #print(root_t,root_s)
        for j in Lt:
            UF[j] = root_s
        #print(edg)
        ans += edg[0]
        #cnt -= 1
    #print(*UF)


print(ans)

Submission status: Accepted

Solution code:
"""
クラスカルのアルゴリズム
"""

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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

# def prim
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)

Submission status: Accepted

Solution code:
# クラスカル法
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])  # costでself.edgesをソートする
        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)

Submission status: Accepted

Solution code:
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):
    # V=ノードの数，e=(s, t, w)のエッジのリスト
    e = sorted(e, key=lambda x: x[2])
    S = DisjointSet(V)
    K = []
    for s, t, w in e:
        # if S.findSet(s) != S.findSet(t):
        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())
    # s, t, w
    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)

Submission status: Accepted

Solution code:
# 2019/07/10

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import heapq


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


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


def unite(x, y):
    link(find_set(x), find_set(y))


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


h = []

line = sys.stdin.readline()
v, e = map(int, line.split())
p = [i for i in range(v)]
rank = [0 for _ in range(v)]

for i in range(e):
    line = sys.stdin.readline()
    s, t, w = map(int, line.split())
    heapq.heappush(h, (w, s, t))

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

print(s)

Submission status: Accepted

Solution code:
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):
        """
        :param u: 始点
        :param v: 終点
        :param d: コスト
        """
        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])  # costでself.edgesをソートする
        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())
graph = Kruskal_UnionFind(V)
for i in range(E):
    s, t, w = map(int, input().split())
    graph.add(s, t, w)

print(graph.Kruskal())

Submission status: Accepted

Solution code:
import heapq

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


class Node():
    def __init__(self, id):
        self.id = id
        self.p = self
        self.rank = 0


class DisjointSet():
    def __init__(self, n):
        self.nodes = {}
        for i in range(n):
            self.makeSet(i)

    def makeSet(self, i):
        self.nodes[i] = Node(i)

    def findSet(self, x):
        if x.p is not x:
            x.p = self.findSet(x.p)
        return x.p

    def unite(self, x, y):
        # ランクの低い方を子にする
        px = self.findSet(x)
        py = self.findSet(y)
        if px.rank > py.rank:
            py.p = px
        else:
            px.p = py
        if x.rank == y.rank:
            py.rank += 1

    def bool(self, x, y):
        return self.findSet(x) == self.findSet(y)


def kruskal(v, edges):
    S = DisjointSet(v)
    K = []

    while len(edges):
        w, edge = heapq.heappop(edges)
        # sorceとtargetがdisjointなら追加
        x, y = S.nodes[edge[0]], S.nodes[edge[1]]
        if not S.bool(x, y):
            S.unite(x, y)
            K.append((edge, w))
    return K


K = kruskal(v, edges)
# print(K)
print(sum(map(lambda x: x[1], K)))

Submission status: Accepted

Solution code:
class UnionFindTree:
    '''
    Union Find Tree
    '''

    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

    def unite(self, x, y):
        self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


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

'''
クラスカルのアルゴリズム
最小全域木の総重み
辺をソートし、UnionFindTreeで同じ集合に属する辺を作らずに集合を構築
'''
e.sort()
uft = UnionFindTree()
for i in range(V):
    uft.make(i)

ans = 0

for w, s, t in e:
    if not uft.same(s, t):
        uft.unite(s, t)
        ans += w

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, v_count: int):
        self.par = [-1]*v_count # 親の番号
        for i in range(v_count):
            self.par[i] = i  # はじめすべての頂点が根
    
    def root(self, x: int) -> int:
        """根を求める"""
        if self.par[x] == x: # if root
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 経路圧縮
            return self.par[x]
    
    def is_same(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        x = self.root(x)
        y = self.root(y)
        if x == y: return
        self.par[x] = y

def kruskal(v_count: int) -> int:
    """O(|E| log|V|)
    return the minimum cost of Spanning Tree"""
    global edges # (w, s, t)
    uf = UnionFind(v_count)
    
    cost = 0
    for w,s,t in sorted(edges): # costが小さい順に
        if not uf.is_same(s, t):
            uf.unite(s, t)
            cost += w
    return cost


if __name__ == "__main__":
    V,E = map(int, input().split())
    edges = []
    for _ in range(E):
        s,t,w = map(int, input().split())
        edges.append((w,s,t))
    ans = kruskal(V)
    print(ans)

Submission status: Accepted

Solution code:
import array
import collections
import heapq
 
 
AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
INF = 2 ** 31 - 1
NO_VERTEX = -1
 
 
# Prim法で頂点0からの最小全域木を求める
def compute_mst_prim(max_v, adj_list):
    # pred[u]は頂点uの「ひとつ前」の頂点を表す
    pred = collections.defaultdict(lambda: NO_VERTEX)
    # uとpred[u]を結ぶ辺の重みがkey[u]に入る
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    # 二分ヒープを優先度付きキューとして用いる
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    # 優先度付きキューに頂点が入っているかを示す配列
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)
 
 
def main():
    max_v, max_e = map(int, input().split())
    adjacency_list = collections.defaultdict(set)
    for _ in range(max_e):
        s, t, w = map(int, input().split())
        adjacency_list[s].add(AdjacentVertex(t, w))
        adjacency_list[t].add(AdjacentVertex(s, w))
    (_, key) = compute_mst_prim(max_v, adjacency_list)
    print(sum(key.values()))
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#クラスカル法 最小全域木を求める

#union-find木
#クラスカル法にはUnion-find木が必要
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] #親
        self.rank = [0 for _ in range(n)] #根の深さ

    #xの属する木の根を求める
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    #xとyの属する集合のマージ
    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

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


#クラスカル法
# V: 頂点集合(リスト) E: 辺集合[始点, 終点, 重み](リスト)
class kruskal():
    def __init__(self, V, E):
        self.V = V
        self.E = E
        self.E.sort(key=lambda x: x[2]) #辺の重みでソート

    def weight(self):
        UF = UnionFind(len(V)) #頂点数でUnion Find Treeを初期化
        res = 0
        for i in range(len(self.E)):
            e = self.E[i]
            
            if (UF.same(e[0], e[1])) == False:
                UF.unite(e[0], e[1])
                res += e[2]
                
        return res

    def edge(self):
        UF = UnionFind(len(V)) #頂点数でUnion Find Treeを初期化
        res_E = []
        for i in range(len(E)):
            e = E[i]
            
            if (UF.same(e[0], e[1])) == False:
                UF.unite(e[0], e[1])
                res_E.append(e)

        return res_E

    def node(self):
        UF = UnionFind(len(V)) #頂点数でUnion Find Treeを初期化
        res_V = []
        for i in range(len(E)):
            e = E[i]
            
            if (UF.same(e[0], e[1])) == False:
                UF.unite(e[0], e[1])
                res_V.append(e[0])
                res_V.append(e[1])

        return list(set(res_V))
        
A, B = map(int, input().split())
E = [list(map(int, input().split())) for _ in range(B)]

V = [i for i in range(A)]

kl = kruskal(V, E)

print(kl.weight())

Submission status: Accepted

Solution code:
import heapq


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

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

cost = 0
roots = [i for i in range(n)]
clusters = {i: {i} for i in range(n)}

while len(edges) > 0:
    w, s, t = heapq.heappop(edges)

    if roots[s] != roots[t]:
        cluster = clusters.pop(roots[t])
        for elem in cluster:
            roots[elem] = roots[s]
        clusters[roots[s]] |= cluster
        cost += w

print(cost)

Submission status: Accepted

Solution code:
par , rank = [],[] #par[x] = yでxの親がyであることを表す rank[x]はxが属する木の高さ

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

def unite(x,y): #x,yが属する集合を合併
    x = find(x)
    y = find(y)
    if (x != y):
        if rank[x] < rank[y]:
            par[x] = y
        else :
            par[y] = x
            if (rank[x] == rank[y]) : rank[x] += 1

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

edge = []

for i in range(e):
    s,t,w = map(int, input().split())
    edge.append((w,s,t))

edge.sort()
mincost = 0

for i in range(v): #初期化　任意の要素が根 
    par.append(i)
    rank.append(0)

for ee in edge:
    w,s,t = ee
    if (find(s) != find(t)) :
        unite(s,t)
        mincost += w

print(mincost)

Submission status: Accepted

Solution code:
num_v,num_e=input().split()

edges=[]
verticies=[]

for i in range(int(num_e)):
    v,u,w=input().split()
    e=(v,u,int(w))
    edges.append(e)


for v in range(int(num_v)):
    v=str(v)
    verticies.append(v)

#for i in range(num_e):
#    e=(e_list[i*3],e_list[i*3+1],int(e_list[i*3+2]))
#    edges.append(e)

graph={
    'verticies':verticies,
    'edges':edges
}


parent={}
g_len={}

def group(v):
    parent[v]=v
    g_len[v]=0

def my_parent(v):
    if parent[v]!=v:
        parent[v]=my_parent(parent[v])
    return parent[v]
    
    
def union(v, u): 
    g_v=my_parent(v)
    g_u=my_parent(u)
    if g_v != g_u:
        if g_len[g_v] >= g_len[g_u]:
            parent[g_u]=parent[g_v]
            g_len[g_v] +=1
        else:
            parent[g_v]=parent[g_u]
            g_len[g_u] +=1
            

def kruskal(graph):
    g_list=[]
    sum_w=0
    
    for v in graph['verticies']:
        group(v)
        
    edges=graph['edges']
    edges.sort(key=lambda edges:edges[2])
    
    for edge in edges:
        v, u, weight =edge
        
        if my_parent(v) != my_parent(u):
            union(v,u)
            g_list.append(edge)
            sum_w=sum_w + weight
            
    return sum_w
    

print(kruskal(graph))

Submission status: Accepted

Solution code:
class DisjointSetElement():
    def __init__(self, x):
        self.parent = x
        self.rank = 0


class DisjointSet():
    def __init__(self, n):
        self.elems = [DisjointSetElement(n) for n in range(n)]

    def _find_set(self, x):
        if x != self.elems[x].parent:
            self.elems[x].parent = self._find_set(self.elems[x].parent)
        return self.elems[x].parent

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

    def _link(self, x, y):
        if self.elems[x].rank > self.elems[y].rank:
            self.elems[y].parent = x
        else:
            self.elems[x].parent = y
            if self.elems[x].rank == self.elems[y].rank:
                self.elems[y].rank += 1

    def unite(self, x, y):
        self._link(self._find_set(x), self._find_set(y))

    def is_alone(self, x):
        return x == self.elems[x].parent


def read_inputs():
    nv, ne = [int(x) for x in input().split()]

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

    return nv, E


def min_sp_tree(nv, E):
    K = DisjointSet(nv)
    total = 0
    n = 0

    i = iter(E)
    while n < nv - 1:
        w, s, t = next(i)
        if not K.same(s, t):
            K.unite(s, t)
            total += w
            n += 1

    return total


def main():
    nv, E = read_inputs()
    E.sort()
    print(min_sp_tree(nv, E))


if __name__ == '__main__':
    main()