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

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


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


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


# xが属する集合の個数
def size(x):
    return -par[find(x)]

# 初期化
# 根なら-size,子なら親の頂点
par = [-1]*V
ans = 0
for e in edges:
    if same(e[1],e[2]):
        continue
    ans += e[0]
    unite(e[1],e[2])
print(ans)

Submission status: Accepted

Solution code:
def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
        else:
            par[a]=b
            if rank[a]==rank[b]:
                rank[b]+=1
def same(a,b):
    return find(a)==find(b)
def Kruskal():
    cost=0
    Edge.sort(key=lambda x:x[2])
    for i in range(E):
        f,t,c=Edge[i]
        if(not same(f,t)):
            union(f,t)
            cost+=c
    return cost

N,E=map(int,input().split())
par=[i for i in range(N)]
rank=[0 for _ in range(N)]
Edge=[]
for i in range(E):
    s,t,w=map(int,input().split())
    Edge.append([s,t,w])
res=Kruskal()
print(res)

Submission status: Accepted

Solution code:
from collections import namedtuple


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

  def is_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.size[a] < self.size[b]:
      a, b = b, a
    self.par[b] = a
    self.size[a] += self.size[b]

  def size_of(self, a):
    return self.size[self.find(a)]

  def find(self, a):
    if a == self.par[a]:
      return a
    self.par[a] = self.find(self.par[a])
    return self.par[a]

Edge = namedtuple('Edge', 'w s t')

V, E = map(int, input().split())
edges = []

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

edges.sort()

u = UnionFind(V)
cost = 0

for w, s, t in edges:
  if u.is_same(s, t):
    continue
  u.unite(s, t)
  cost += w

print(cost)

Submission status: Accepted

Solution code:
from collections import defaultdict

class Graph:

    def __init__(self,vertices):
        self.V = vertices
        self.graph = []

    def addEdge(self,s,t,w):
        self.graph.append([s,t,w])

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

    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)

        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot

        else :
            parent[yroot] = xroot
            rank[xroot] += 1

    def KruskalMST(self):
        sum = 0
        result = []
        i = 0
        e = 0

        self.graph = sorted(self.graph, key=lambda item:item[2])
        parent = []
        rank = []
        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        while e < self.V - 1:
            s, t, w = self.graph[i]
            i+=1
            x = self.find(parent, s)
            y = self.find(parent, t)

            if x != y:
                e = e + 1
                result.append([s, t, w])
                self.union(parent, rank, x, y)

        for s,t,weight in result:
            sum +=  weight

        print(sum)

if __name__ == "__main__":
    V, E = (int(z) for z in input().split())
    g = Graph(V)

    for i in range(E):
        s, t, w = (int(z) for z in input().split())
        g.addEdge(s, t, w)

    g.KruskalMST()

Submission status: Accepted

Solution code:
# 最小全域木（Kraskal法　＋　UnionFind）
class UnionFind:

    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)
        # print(self.rank)

    # 検索
    def findSet(self, x):
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        else:
            # 根でないなら、親の要素で再走査
            # 走査する過程で親を書き換える(根を親につなぎなおす)
            self.par[x] = self.findSet(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        # 根を探す
        x = self.findSet(x)
        y = self.findSet(y)
        # 木の高さを比較し,高いほうに低いほうをくっつける
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            # 木の高さが同じなら片方の木の高さを1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.findSet(x) == self.findSet(y)


# Kruskal法により最小全域木を求める
def compute_mst_kruskal(v, edges):
    # 重みの昇順で辺(edge)を並べ替える（あとで重みが最小のものから順番に走査するので）
    #重み(x[2])をkeyにしてソート
    edges = sorted(edges,key=lambda x: x[2])
    # | V |でUnionFind作成
    uf = UnionFind(v)
    mst = []

    # edgesが空になるまで繰り返す
    """
    for edge in edges:
        # ふたつの頂点が同じ木（集合）に属していないなら二つの木を連結する
        if not uf.in_the_same_set(edge.start, edge.end):
            uf.unite(edge.start, edge.end)
            mst.append(edge)
    return mst
    """
    i = 0
    # 重みが小さい順に辺を走査していく
    while i < len(edges):
        # 最小の辺を選択
        edge = edges[i]

        """
        start : 選択された辺の始点
        end   : 選択された辺の終点
        無向グラフなのでstart,end自体に大きな意味はない
        """
        start = edges[i][0]
        end   = edges[i][1]

        # start,endが同じ木に属していなかったら
        if not uf.same_check(start, end):
            #print(edge)
            uf.union(start,end)
            mst.append(edge)
        i = i + 1
    return mst

def buble_sort(tdlist):
    i=0
    while i < len(tdlist)-1:
        if tdlist[i][2] > tdlist[i+1][2]:
            tmp = tdlist[i]
            tdlist[i] = tdlist[i+1]
            tdlist[i+1] = tmp
            i = -1
        i = i + 1

    #print(tdlist)
    return tdlist


def main():
    #print()
    p = []  ##appendのために宣言が必要
    v, e = map(int, input().split())
    # v：頂点数
    # e：辺
    # 入力受付
    i = 0
    while i < e:
        try:
            p.append(list(map(int, input().split())))
            i = i + 1
        except:
            break;

    mst = compute_mst_kruskal(v, p)
    #print(sum(e.weight for e in mst))


    i = 0
    total_weight = 0
    while i < len(mst):
        total_weight = total_weight + mst[i][2]
        i = i + 1
    print(total_weight)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    # この時点でそれぞれのノードは自分を親としている
    # 初期化時に問題が0の頂点を認めるかに注意すること
    def __init__(self, n):
        self.N = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    # xの根を返す関数
    def root(self, x):
        visited_nodes = []
        while True:
            p = self.parent[x]
            if p == x:
                # 縮約
                for node in visited_nodes:
                    self.parent[node] = x
                return x
            else:
                visited_nodes.append(x)
                x = p

    # 木の結合を行う。親の配下に入る
    def unite(self, x, y):
        if not self.root(x) == self.root(y):
            if self.rank[x] > self.rank[y]:
                self.parent[self.root(y)] = self.root(x)
            else:
                self.parent[self.root(x)] = self.root(y)
                if self.rank[x] == self.rank[y]:
                    self.rank[self.root(y)] += 1

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

    # 木の根に到達すまでにたどるノードの配列を返す
    def printDebugInfo(self):
        print([self.root(i) for i in range(self.N)])


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

tree = UnionFind(V)

weight = 0
counter = 0
for edge in edges:
    if tree.ifSame(edge[1], edge[2]):
        continue
    else:
        tree.unite(edge[1], edge[2])
        weight += edge[0]
        counter += 1
    if counter == V-1:
        break

print(weight)

Submission status: Accepted

Solution code:
import heapq

def makeSet(x):
    p[x] = x
    rank[x] = 0

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] += 1

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



v,e = map(int, input().split())
edge = [[] for _ in range(v)]

p = [0]*v
rank = [0]*v
for x in range(v):
    makeSet(x)

S = []
ans = 0
for _ in range(e):
    s,t,w = map(int, input().split())
    heapq.heappush(S, [w, s, t])
    
while S:
    w,s,t = heapq.heappop(S)
    if findSet(s) != findSet(t):
        union(s,t)
        ans += w
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())
G = []
for _ in range(E):
    s, t, w = map(int, input().split())
    G.append((w, s, t))
G.sort()
ans = 0
uf = UnionFind(V)
# print(G)
for i in range(E):
    if not uf.same(G[i][1], G[i][2]):
        ans += G[i][0]
        uf.union(G[i][1], G[i][2])

print(ans)

Submission status: Accepted

Solution code:
import heapq
def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist):
        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)]
#隣接リスト edge[i]:[コスト,行先]
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())

Submission status: Accepted

Solution code:
import sys
import queue
sys.setrecursionlimit(10 ** 6)


class UnionFind:
    def __init__(self, n):
        self.parents = [-1] * n  # 各ノードの親を保存する。 idx 番号がノードに相当する
        self.rank = [0] * n  # 各ノードのrank　を保存する。 idx 番号がノードに相当する

    def root(self, x):  # ノードの一番上の親を返す。
        if self.parents[x] == -1:  # self.parents が変化していないならば根である。
            return x
        self.parents[x] = self.root(self.parents[x])
        return self.parents[x]

    def unite(self, x, y):
        x_root = self.root(x)
        y_root = self.root(y)

        if x_root == y_root:  # すでに同一の木に属している場合
            return

        if self.rank[x_root] < self.rank[y_root]:
            self.parents[x_root] = y_root  # 大きい木に小さい木を接続する。　self.root の処理が軽くなるから。
        elif self.rank[x_root] == self.rank[y_root]:
            self.parents[x_root] = y_root
            self.rank[y_root] += 1
        else:
            self.parents[y_root] = x_root
        return

    def is_in_same(self, x, y):  # 同じ木に属しているか確認する。
        if self.root(x) == self.root(y):
            return True
        else:
            return False


def main():
    v, e = map(int, sys.stdin.readline().strip().split())

    edges = []
    for _ in range(e):
        s, t, w = map(int, sys.stdin.readline().strip().split())
        edges.append((s, t, w))

    edges = sorted(edges, key=lambda x: x[2])  # 辺の重みで昇順ソート

    ans = 0  # 最小全域木の辺の重みの総和

    unionfind = UnionFind(v)
    for s, t, w in edges:
        if unionfind.is_in_same(s, t):
            continue
        else:
            unionfind.unite(s, t)
            ans += w

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

class UnionFind:
    def __init__(self, n):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.find(self.d[x])
    
    def unite(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):
        if self.find(x)==self.find(y):
            return True
        return False
    
    def size(self, x):
        return (-1) * self.d[self.find(x)]

V, E = mi()
stw = li2(E)
stw.sort(key=lambda x: x[2])

T = UnionFind(V)
cnt = 0

for i in range(E):
    s, t, w = stw[i][0], stw[i][1], stw[i][2]
    if not T.same(s, t):
        T.unite(s, t)
        cnt += w

print(cnt)

Submission status: Accepted

Solution code:

rank = []
p = []


def makeSet(x):
    p.append(x)
    rank.append(0)


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 same(x, y):
    return findSet(x) == findSet(y)

def kruskal(g):
    MST = 0
    edges = g

    for e in edges:
        u = e[0]
        v = e[1]


        if findSet(u) != findSet(v):
            union(u, v)
            MST += e[2]

    return MST


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

for i in range(V):
    makeSet(i)

print(kruskal(G))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
def prim(n, graph):
    used = [False] * n
    hq = [(w, v) for v, w in graph[0]]
    heapify(hq)
    used[0] = True
    res = 0
    while hq:
        w, v = heappop(hq)
        if used[v]:
            continue
        used[v] = True
        res += w
        for cv, cw in graph[v]:
            if used[cv]:
                continue
            heappush(hq, (cw, cv))
    return res

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

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())
stw = [ list(map(int,input().split())) for _ in range(e) ]

T = Kruskal_UnionFind(v)
for i in range(e):
    s = stw[i][0] - 1
    t = stw[i][1] - 1
    w = stw[i][2]
    T.add(s,t,w)

print(T.Kruskal())

Submission status: Accepted

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

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

    # xとyの属する集合の併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        # sizeの大きいほうがx
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x

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

    # xが属する集合の個数
    def size(self, x):
        return -self.parent[self.find(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()
uf = UnionFind(V)
ans = 0
for edge in edges:
    if uf.same(edge[1], edge[2]):
        continue
    ans += edge[0]
    uf.unite(edge[1], edge[2])
print(ans)

Submission status: Accepted

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

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(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.root(x) == self.root(y)


def main():

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

    # need sorted
    edge_q = sorted([tuple(map(int, input().split())) for _ in range(E)], key=lambda x: x[2])

    # kruskal
    ans = 0
    forest = UnionFind(V)
    for s, t, w in edge_q:
        if forest.same(s, t):
            continue
        forest.unite(s, t)
        ans += w
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
H = []
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))
    heapq.heappush(H, (w, s, t))


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

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

    def size(self, a):
        return - self.parent[self.root(a)]

    def connect(self, a, b) -> bool:
        a = self.root(a)
        b = self.root(b)

        if a == b:
            return False

        if self.size(a) < self.size(b):
            a, b = b, a

        self.parent[a] += self.parent[b]
        self.parent[b] = a
        return True


unif = UnionFind(V)
ans = 0
while len(H) > 0:
    w, s, t = heapq.heappop(H)
    if unif.root(s) == unif.root(t):
        continue

    unif.connect(s, t)
    ans += w

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
from heapq import heappush, heappop, heapify
    
def prim(V, E, v=0):
    # E[v] = (cost, u)
    
    visited = [False] * V
    visited[v] = True
    count = V-1
    
    dist = [float('inf')] * V
    dist[v] = 0
    
    q = list(E[v])
    heapify(q)
    
    for c, u in E[v]: dist[u] = c
    
    while count and q:
        c, v = heappop(q)

        if visited[v]: continue
    
        visited[v] = True
        count -= 1
        
        for c, u in E[v]:
            if visited[u]: continue
            dist[u] = min(dist[u], c)
            heappush(q, (dist[u], u))
    
    return dist

def main():
    V, e = map(int, input().split())
    E = [[] for i in range(V)]
    
    for i in range(e):
        v, u, c = map(int, input().split())
        E[v].append((c, u))
        E[u].append((c, v))

if __name__ == '__main__':
    V, e = map(int, input().split())
    
    E = deque(deque() for i in range(V))
    
    for i in range(e):
        v, u, c = map(int, input().split())
        
        E[v].append((c, u))
        E[u].append((c, v))
        
    print(sum(prim(V, E)))

Submission status: Accepted

Solution code:

import heapq

def main():
    n,m = map(int,input().split())
    e = [[] for _ in range(n)]
    for _ in range(m):
        a,b,c = map(int,input().split())
        e[a].append([b,c])
        e[b].append([a,c])

    inf = 1000000007
    d = [inf]*n
    d[0] = 0
    visited = [False]*n
    pq = [[0,0]]
    heapq.heapify(pq)
    while pq:
        c,v = heapq.heappop(pq)
        visited[v] = True
        for u,nc in e[v]:
            if not visited[u] and nc < d[u]:
                d[u] = nc
                heapq.heappush(pq,[nc,u])

    res = 0
    for i in range(n):
        res+=d[i]
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        # negative value: represents the root of a tree; its absolute value is the size of the tree
        # positive value: the parent's index
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        
    def find(self, v):
        if self.vertices[v] < 0: # v is a root
            return v
        else:
            # path compression: reconnect v to the root
            self.vertices[v] = self.find(self.vertices[v])
            return self.vertices[v]
        
    def union(self, u, v):
        s1 = self.find(u) # the root of the tree including vertex u
        s2 = self.find(v) # the root of the tree including vertex v
        
        if s1 == s2: # u and v is in the same tree
            return False
        
        if self.rank[s1] > self.rank[s2]: # the tree including u is taller
            self.vertices[s1] += self.vertices[s2] # update the size of the bigger tree
            self.vertices[s2] = s1
        else: # the tree including v is taller
            self.vertices[s2] += self.vertices[s1] # update the size of the bigger tree
            self.vertices[s1] = s2
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]

class Kruskal:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = []

    def add_edge(self, init, end, weight):
        self.E.append((weight, init, end))
        
    def min_spanning_tree(self):
        N, E = self.N, self.E
        weight = 0; edges = []
        n_edges = 0
        uf = UnionFind(N) # for judging connectivity
        E = sorted(E)
        for w, a, b in E:
            if uf.union(a, b):
                edges.append((a, b))
                n_edges += 1; weight += w
            if n_edges == N - 1: break
        return edges, weight

N, M = map(int, input().split())
kr = Kruskal(N)
for _ in range(M):
    a, b, c = map(int, input().split())
    kr.add_edge(a, b, c)
_, ans = kr.min_spanning_tree()
print(ans)

Submission status: Accepted

Solution code:
v, e = map(int, input().split())
p = [i for i in range(v)]
E = [list(map(int, input().split())) for _ in range(e)]

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

def root(x):
  if p[x]==x:
    return x
  p[x] = root(p[x])
  return p[x]

ans = 0
for edg in E:
    a, b, w = edg
    if root(a)!=root(b):
        ans += w
        p[root(a)] = root(b)

print(ans)

Submission status: Accepted

Solution code:
V_0, E_0 = map(int, input().split())
from collections import deque
V = [False]*V_0
V[0] = True
E = 0
import heapq

S = []
heapq.heapify(S)
graph = [[] for i in range(V_0)]

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

for w, a in graph[0]:
    heapq.heappush(S, (w, a))

while len(S)!=0:
    w, a = heapq.heappop(S)
    if V[a]:
        continue
    for w2, b in graph[a]:
        if not V[b]:
            heapq.heappush(S, (w2, b))
    V[a] = True
    E += w

print(E)

Submission status: Accepted

Solution code:
import sys 
MOD = 10 ** 9 + 7
INF = 10**11
from heapq import heapify,heappush,heappop

def prim(n,G):
    ans = 0
    used = [0] * n
    used[0] = 1
    q = []
    for e,c in G[0]:
        heappush(q,(c,e))
    
    while len(q):
        c1,e1 = heappop(q)
        if used[e1]:
            continue
        used[e1] = 1
        for e2,c2 in G[e1]:
            if used[e2] == 0:
                heappush(q,(c2,e2))
        ans += c1
    return ans

def main():
    n,m = map(int,input().split())
    G = [[] for _ in range(n)]
    for _ in range(m):
        a,b,c = map(int,input().split())
        G[a].append((b,c))
        G[b].append((a,c))
    ans = prim(n,G)
    print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
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が属するグループと要素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): #要素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())

#print(list(uf.all_group_members().values())) #グループ一覧を表示
#0-indexed n=5なら頂点の名前は0,1,2,3,4
import sys
input=sys.stdin.readline
v,e=map(int,input().split())
uf=UnionFind(v)
lis=[]
for i in range(e):
    x,y,w=map(int,input().split())
    lis.append([w,x,y])
import heapq
heapq.heapify(lis)

ans=0
for i in range(e):
    w,x,y=heapq.heappop(lis)
    if uf.same(x,y)==False:
        ans+=w
        uf.union(x,y)
    else:
        pass
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)  # -1ならそのノードが根,で絶対値が木の要素数
        self.rank = [0] * (n + 1)

    def find(self, x):  # xの根となる要素番号を返す
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

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

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

    def getNodeLen(self, x):
        return -self.root[self.find(x)]


if __name__ == "__main__":
    N, M = map(int, input().split())
    edge = [tuple(map(int, input().split())) for _ in range(M)]
    edge.sort(key=lambda x: x[2])

    ans = 0
    uf = UF_tree(N)
    for s, t, c in edge:
        if uf.isSame(s, t):
            continue
        ans += c
        uf.unite(s, t)
    print(ans)

Submission status: Accepted

Solution code:
from heapq import *
def prim_heap():
    used = [False] * n
    e_lst = []
    for e in edge[0]:
        heappush(e_lst,e)
    used[0] = True
    res = 0
    while e_lst:
        e_min = heappop(e_lst)
        v = e_min[1]
        if used[v]: continue
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(e_lst, e)
        res += e_min[0]
    return res

n, k = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(k):
    s, t, w = map(int, input().split())
    edge[s].append((w, t))
    edge[t].append((w, s))
print(prim_heap())