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:
num_V, num_E = map(int, input().split())

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

        if x == y:
            return

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

        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]

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

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

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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

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

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

uf = UnionFind(num_V)
ans = 0

for s, t, w in root:
    if uf.same(s,t):
        continue
    else:
        uf.union(s,t)
        ans += w

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys


class PriorityQueue:
    def __init__(self):
        self._queue = []

    def push(self, value):
        heappush(self._queue, value)

    def pop(self):
        return heappop(self._queue)

    @property
    def empty(self):
        return not self._queue

    def __len__(self):
        return len(self._queue)

    def __contains__(self, item):
        return item in self._queue


v, e = map(int, input().split())
if v == 1:
    print(0)
    sys.exit()
edge = [[] for _ in range(v)]
for _ in range(e):
    s, t, w = map(int, input().split())
    # 無向グラフ
    edge[s].append((w, t))
    edge[t].append((w, s))

V = set()
pq = PriorityQueue()
weight = 0
V.add(0)
for i in edge[0]:
    pq.push(i)

while True:
    nw, nv = pq.pop()
    if nv in V:
        continue
    else:
        weight += nw
        V.add(nv)
        for i in edge[nv]:
            pq.push(i)

    if len(V) == v:
        break

print(weight)

Submission status: Accepted

Solution code:
class Edge:
    def __init__(self, u, v, cost):
        self.u = u
        self.v = v
        self.cost = cost
    
    def __str__(self):
        return "u: " + str(self.u) + " v: " + str(self.v) + " cost: " + str(self.cost)

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
    
    def isSame(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    V, E = map(int,input().split())
    edges = []
    for i in range(E):
        s,t,w = map(int,input().split())
        e = Edge(s,t,w)
        edges.append(e)
    
    edges.sort(key=lambda e: e.cost)

    uf = UnionFind(V+1)

    ans = 0
    for edge in edges:
        if not uf.isSame(edge.u, edge.v):
            uf.unite(edge.u, edge.v)
            ans += edge.cost

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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

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

    cost = 0
    for edge in edges:
        w, s, t = edge
        if not uf.same(s, t):
            cost += w
            uf.union(s, t)
    print(cost)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

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

visited = [False]*V
visited[0] = True
q = []
node = 0
node_cnt = 1
ans = 0

while node_cnt < V:
    for adj,w in C[node]:
        if not visited[adj]:
            heapq.heappush(q,(w,adj))
    while 1:
        weight,node = heapq.heappop(q)
        if not visited[node]:
            break
    visited[node] = True
    ans += weight
    node_cnt += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(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)
V, E = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(E)]
X = sorted(X, key = lambda x:x[2])
UF = UnionFind(V)
ans = 0
for i in range(E):
    a, b = X[i][0]+1, X[i][1]+1
    if not UF.same_check(a, b):
        UF.union(a, b)
        ans += X[i][2]
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.parents[y] = x


V, E = map(int, input().split())
q = []
K = {}
ans = 0
S = UnionFind(V)

for _ in range(E):
    s, t, w = map(int, input().split())
    heappush(q, (w, s, t))
#print(q)
# クラスカル法
while len(q) > 0:
    w, s, t = heappop(q)
    if S.find(s) != S.find(t):
        ans += w
        S.union(s,t)
print(ans)

Submission status: Accepted

Solution code:
import heapq
from itertools import accumulate

v, e = map(int, input().split())
g = [[] for _ in range(v)]
for i in range(e):
    s, t, d = map(int, input().split())
    g[s].append((d, t))#(重み, 次の頂点)
    g[t].append((d, s))#(重み, 次の頂点)

visitedv = [False] * v
visitedv[0] = True
#visitede = []
visitede = 0
candidate = []
for i in g[0]:
    heapq.heappush(candidate, i)
while len(candidate):
    #まだ使われていない頂点から最小のものを探す
    minedge = heapq.heappop(candidate)#(重み, 頂点)
    if visitedv[minedge[1]]:
        continue
    c = minedge[1]
    visitedv[c] = True
    #visitede.append(minedge[0])
    visitede += minedge[0]
    for i in g[c]:
        if not visitedv[i[1]]:
            heapq.heappush(candidate, i)

#print(list(accumulate(visitede))[-1])
print(visitede)

Submission status: Accepted

Solution code:
from heapq import heapify
from heapq import heappop
from heapq import heappush
class UnionFind():
    def __init__(self, n):  #初期化　最初はみんなばらばら
        self.n = n
        self.parents = [-1] * n
    def find(self, x):  #xの根を見つける　たどった経路全ての根を更新
        if self.parents[x] < 0:
            return x   #根の番号を返す
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)  #x,yの木の根
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x  #xをでかい木にする

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

    def size(self, x):  #xの含まれる木の要素数を返す
        return -self.parents[self.find(x)]

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

    def members(self, x):  #xの含まれる木の要素を配列で返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):  #根をすべて返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self): #木の個数
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
V,E = map(int,input().split())
uf = UnionFind(V)
hq = []
heapify(hq)
for i in range(E):
    s,t,w = map(int,input().split())
    heappush(hq,(w,s,t))
ans = 0 #最小全域木の辺の重みの総和
while len(hq) != 0:
    w,s,t = heappop(hq)
    if not uf.same(s,t):
        ans += w
        uf.union(s,t)
    else:
        continue
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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

v, e = map(int,input().split())
road = []
for i in range(e):
    a, b, c = list(map(int,input().split()))
    road.append((a,b,c))
road.sort(key = lambda x: x[2])
#print(road)

uf = UnionFind(v)
cost = 0
cnt = 0
for i in range(e):
    a = road[i][0]
    b = road[i][1]
    c = road[i][2]
    if uf.same(a,b) == False:
        uf.union(a,b)
        cost += c
        cnt += 1
        if cnt == v-1:
            break
#print("cost =", cost)
print(cost)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
        self.rank=[0]*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.rank[x]<self.rank[y]:
            self.parents[y]+=self.parents[x]
            self.parents[x]=y
        else:
            self.parents[x]+=self.parents[y]
            self.parents[y]=x

            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

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

    def element_count(self,x):
        x=self.find(x)
        return -self.parents[x]

    def group_count(self):
        count=0
        for e in self.parents:
            if e<0: count+=1
        return count

def kruskal(n,edges):
    u=UnionFind(n)
    ans=0
    for x in edges:
        s,t,w=x
        if u.are_same(s,t)==False:
            u.union(s,t)
            ans+=w

    return ans

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    v,e=map(int,readline().split())
    edges=[list(map(int,readline().split())) for _ in range(e)]
    edges.sort(key=lambda x:x[2])
    print(kruskal(v,edges))

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")

import sys,collections
sys.setrecursionlimit(10000)

INF = float("inf")

V,E = map(int,sys.stdin.readline().split())
stw = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(E)) # multi line with multi param

# n x n adjacency matrix
#G = [[-1,2,3],[2,-1,3],[1,2,-1]]
# G = [{} for _ in range(V)]
# for s,t,w in stw:
#     G[s][t] = w
#     G[t][s] = w
wst = [[w,s,t] for s,t,w in stw]
wst.sort()

parents = list(range(V))
def find(x):
  while parents[x] != x:
    x = parents[x]
    parents[x] = parents[parents[x]]
  return x

def union(s,t):
  sp = find(s)
  tp = find(t)
  if sp == tp:
    pass
  elif sp < tp:
    parents[sp] = tp
  else:
    parents[tp] = sp

INF = float("inf")
ret = 0
for w,s,t in wst:
    if find(s) != find(t):
        union(s,t)
        ret += w
print(ret)

Submission status: Accepted

Solution code:
class unionfind:
    sz = 0
    par = []
    def __init__(self, n):
        self.sz = n
        for i in range(n):
            self.par.append(-1)

    def find(self, a):
        if self.par[a]<0: return a
        self.par[a] = self.find(self.par[a])
        return self.par[a]
    
    def size(self, a):
        a = self.find(a)
        return -self.par[a]
    
    def same(self, a,b):
        return self.find(a) == self.find(b)

    def unite(self, a,b):
        a = self.find(a)
        b = self.find(b)
        if self.same(a,b): return False
        if self.size(a) < self.size(b):
            a,b=b,a
        self.par[a] += self.par[b]
        self.par[b] = a
        return True

n,m = map(int,input().split())
g = []
for i in range(m):
    s,t,w = map(int,input().split())
    g.append([w,s,t])
g = sorted(g)
ans = 0
uni = unionfind(n)
for c,i,j in g:
    if uni.unite(i,j): ans += c
print(ans)

Submission status: Accepted

Solution code:
import heapq

n,e=map(int,input().split())
G=[[] for _ in range(n)]
for index in range(e):
    s,t,w=map(int,input().split())
    #要素はリスト
    G[s].append([w,t])
    G[t].append([w,s])

#ノード0から始める
def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in G[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 G[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

ans=prim_heap()
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, V):
        self.group = [i for i in range(V)]
        self.rank = [0] * V

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

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

class Edge:
    def __init__(self, FROM, TO, WEIGHT):
        self.FROM = FROM
        self.TO = TO
        self.WEIGHT = WEIGHT

    def __lt__(self, arg):
        return self.WEIGHT < arg.WEIGHT

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

UF = UnionFind(V)

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

ans = 0
for i in range(E):
    if UF.is_same_group(G[i].FROM, G[i].TO):
        continue
    UF.unite(G[i].FROM, G[i].TO)
    ans += G[i].WEIGHT

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

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

    edges[s-1].append([w, t-1])
    edges[t-1].append([w, s-1])

# プリム法
def prim(n, w, edges):
    used = [True] * n #True:不使用
    edgelist = []
    for e in edges[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 edges[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

print(prim(V, E, edges))

Submission status: Accepted

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

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

Edges.sort(key=lambda x:x[2])
F=UnionFind(V)
cost=0
for e in Edges:
    if F.same(e[0],e[1]):
        continue
    F.union(e[0],e[1])
    cost+=e[2]
print(cost)

Submission status: Accepted

Solution code:
import sys, heapq
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

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 kruskal(es, V):
    es.sort(key=lambda x:x[2])
    uf = UnionFind(V)
    res = 0
    for e in es:
        if not uf.same(e[0], e[1]):
            uf.union(e[0], e[1])
            res += e[2]
    return res

def resolve():
    V, E = LI()
    es = [[[]] for _ in range(E)]
    for i in range(E):
        s, t, w = LI()
        es[i] = [s, t, w]

    print(kruskal(es, V))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
#UnionFind木
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 nums(self,x):
        return abs(self.parents[self.find(x)])

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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

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

N, M = map(int, input().split())
edges = []*M
for i in range(M):
    a,b,w = map(int, input().split())
    edges.append((w,a,b))

edges.sort()

uf = UnionFind(N)
ans = 0
for i in range(M):
    u,x,y = edges[i]
    if not uf.same(x,y):
        uf.union(x,y)
        ans += u
print(ans)

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

class UnionFind:
    def __init__(self, n):
        # 初期状態は全要素が根なので、親は自分自身
        self.par = [i for i in range(n+1)]
        # 集団の要素数(size)を格納する(初期は全て1)
        self.size = [1] * (n+1)
    
    # 根を検索する関数
    def find(self, x):
        # 根までたどったらその番号を返す
        if self.par[x] == x:
            return x
        # 根でないなら親の要素で再検索
        else:
            # 検索過程で親を書き換える(圧縮経路)
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])
  
    # 結合(unite)する関数
    def unite(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        # サイズを比較し、小さい方を大きい方に繋げる
        if self.size[x] < self.size[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
           
    # 同じグループに属するかを判定する関数
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    # 要素が属する木のサイズを返す関数
    def get_size(self, x):
        return self.size[self.find(x)]
    
    # グループ数を返す関数
    def group_sum(self):
        c = 0
        for i in range(len(self.par)):
            if self.find(i) == i:
                c += 1
        return c


def main():
    V,E,*stw = map(int, read().split())

    Edges = []
    for s, t, w in zip(*[iter(stw)]*3):
        Edges.append((s, t, w))
    
    Edges.sort(key=lambda x: x[2])
    
    uf = UnionFind(V)
    ans = 0
    for s, t, w in Edges:
        if uf.is_same(s, t):
            continue
        else:
            ans += w
            uf.unite(s, t)

    print(ans)
   

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
v, e = map(int, input().split())
G = [[] for _ in range(v)]
for _ in range(e):
    s, t, w = map(int, input().split())
    G[s].append((w,t))
    G[t].append((w,s))
been = [0]*v
ans = 0
# print(G)
queue = []
a = (0,0)
heappush(queue,a)
been[0] = 1
# print(heappop(queue))
while sum(been) != v:
    while len(queue):
        a = heappop(queue)
        if been[a[1]] == 0:
            been[a[1]] = 1
            break
    
    ans += a[0]
    # print(been,a,ans,queue)
    for nex in G[a[1]]:
        heappush(queue, (nex[0], nex[1]))
print(ans)

Submission status: Accepted

Solution code:
import heapq
v,e=map(int,input().split())
edge=[]
for i in range(e):
  s,t,w=map(int,input().split())
  edge.append([w,s,t])
heapq.heapify(edge)
class UnionFind:
  def __init__(self,n):
    self.n=n
    self.r=[i for i in range(n)]
    self.rank=[1 for i in range(n)]
    self.cost=0
  def find(self,x):
    if x==self.r[x]:
      return x
    else:
      self.r[x]=self.find(self.r[x])
      return self.r[x]
  def union(self,x,y,c):
    rx=self.find(x)
    ry=self.find(y)
    if rx==ry:
      return
    if self.rank[ry]>self.rank[rx]:
      rx,ry=ry,rx
    self.r[ry]=rx
    self.rank[rx]+=self.rank[ry]
    self.cost+=c
uf=UnionFind(v)
while edge:
  path=heapq.heappop(edge)
  if uf.find(path[1])==uf.find(path[2]):
    continue
  uf.union(path[1],path[2],path[0])
print(uf.cost)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from pprint import pprint

INF = float('inf')

n_nodes, m_edges = map(int, input().split())
edges = []
for _ in range(m_edges):
    u, v, w = map(int, input().split())
    edges.append([u, v, w])
# pprint(edges)

edges_sorted = sorted(edges, key=lambda e: e[2])
# pprint(edges_sorted)


# Kruskal's algorithm
def find_root(v, parents):
    if v == parents[v]:
        return v
    parents[v] = find_root(parents[v], parents)
    return parents[v]


def has_same_root(u, v, parents):
    return find_root(u, parents) == find_root(v, parents)


def unite(u, v, parents):
    root_u = find_root(u, parents)
    root_v = find_root(v, parents)
    parents[root_u] = root_v
    return parents


parents = [i for i in range(n_nodes)]
res = 0
for u, v, w in edges_sorted:
    if not has_same_root(u, v, parents):
        res += w
        parents = unite(u, v, parents)
print(res)

Submission status: Accepted

Solution code:
import heapq
def set_heapq(que, edge, used, v, add_dist=0):
    '''
    確定地点vからつながる辺を全てqueに設定し、返却する

    Parameters
    que : heapque(touple or list)
        辺を管理するキュー (距離、次の行き先)のtopuleまたはlistにて管理
    edge : list
        全ての辺を格納する二次元のリスト edge[0]にてノード0から伸びる辺であることを表し、
        edge[0] → [距離、次の行き先] を表すlistが格納されている
    v : int
        グラフ上のノード ダイクストラでは確定したノードがvにあたる
    add_dist : int
        確定した地点に足し合わせる距離 スタート地点以外では何かしらの値が追加されることになる

    Returns
    que : heapque(touple or list)
        引数queにvからつながる辺を追加したキュー
    '''
    for a,b in edge[v]:
        if used[b]:
            heapq.heappush(que,(a+add_dist,b))
    return que

def prim_heap(edge, n):
    '''
    プリム法で最小全域木を求める

    Parameters
    edge : list
        全ての辺を格納する二次元のリスト edge[0]にてノード0から伸びる辺であることを表し、
        edge[0] → [距離、次の行き先] を表すlistが格納されている
    
    Returns
    res : int
        最小全域木の全ての辺のコストの総和
    '''
    used = [True] * n #True:不使用
    edgelist = []
    edgelist = set_heapq(edgelist, edge, used, 0)
    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
        edgelist = set_heapq(edgelist, edge, used, v)
        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(edge, V))

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
inf = float("inf")
white = 0; gray = 1; black =2

def prim():
    mindist[0] = 0 
    PQ = [(0,0)]
    while PQ:
        minw,s = heappop(PQ)
        color[s] = black
        if mindist[s] < minw: continue
        for t,w in G[s]:
            if color[t] == black: continue
            if w < mindist[t]:
                mindist[t] = w
                color[t] = gray
                heappush(PQ,(w,t))
    return sum(mindist)

V,E = map(int,input().split())
G = [[] for _ in range(V)]
for _ in range(E):
    s,t,w = map(int,input().split())
    G[s].append((t,w))
    G[t].append((s,w))
color = [white]*V
mindist = [inf]*V
print(prim())

Submission status: Accepted

Solution code:
import sys
import copy
import heapq
from collections import deque

# sys.setrecursionlimit(100001)
INF = sys.maxsize


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

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

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

            if x == y:
                return

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

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

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

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

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

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}

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

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

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

    edges.sort()

    ans = 0
    for d,s,t in edges:
        if tree.same(s,t):
            continue
        tree.union(s,t)
        ans += d

    print(ans)

# ===main===
if __name__ == '__main__':
    main()