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: Memory Limit Exceeded

Solution code:
from collections import defaultdict
import heapq

vertices,edges = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)

for e in range(edges):
    source,target,w = map(int,input().split(" "))
    link[source] = link.get(source,set()) | {target}
    link[target] = link.get(target,set()) | {source}
    weight[source].update({target:w})
    weight[target].update({source:w})
queue = []
heapq.heapify(queue)
heapq.heappush(queue,[0,0])
went = set()
now_weight = 0

while len(went) < vertices:
    here_weight,here = heapq.heappop(queue)
    #print(now_weight,here)
    now_weight += here_weight
    can_go = link.get(here,set()) - went
    min_weight,next_t = float("inf"),-1
    for c in can_go:
        #heapq.heappush(queue,[now_weight + weight[here][c],c])
        if c not in went:
            heapq.heappush(queue,[weight[here][c],c])
    #print(queue)
    went = went | {here}
print(now_weight)

Submission status: Accepted

Solution code:
import sys


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

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

    def unite(self, ver1, ver2):
        ver1, ver2 = self.find(ver1), self.find(ver2)
        if ver1 == ver2:
            return
        if self.rank[ver1] < self.rank[ver2]:
            ver1, ver2 = ver2, ver1
        self.par[ver2] = ver1
        if self.rank[ver1] == self.rank[ver2]:
            self.rank[ver1] += 1

    def same(self, ver1, ver2):
        return self.find(ver1) == self.find(ver2)


class Kruskal:

    class Edge:
        def __init__(self, u, v, cost):
            self.u, self.v, self.cost = u, v, cost

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

    def __init__(self, node_size):
        self._node = node_size
        self._edge_list = []

    def add_edge(self, u, v, cost):
        self._edge_list.append(self.Edge(u, v, cost))

    def solve(self):
        uf = UnionFind(self._node)
        res = 0
        edge_count = 0
        sorted_edge_list = sorted(self._edge_list)
        for e in sorted_edge_list:
            if not uf.same(e.u, e.v):
                uf.unite(e.u, e.v)
                res += e.cost
                edge_count += 1
                if edge_count == self._node-1:
                    break
        return res

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
    kr = Kruskal(n)
    for _ in range(m):
        s, t, w = map(int, sys.stdin.readline().split())
        kr.add_edge(s, t, w)
    print(kr.solve())

Submission status: Accepted

Solution code:
import sys


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

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

    def unite(self, ver1, ver2):
        ver1, ver2 = self.find(ver1), self.find(ver2)
        if ver1 == ver2:
            return
        if self.rank[ver1] < self.rank[ver2]:
            ver1, ver2 = ver2, ver1
        self.par[ver2] = ver1
        if self.rank[ver1] == self.rank[ver2]:
            self.rank[ver1] += 1

    def same(self, ver1, ver2):
        return self.find(ver1) == self.find(ver2)


class Kruskal:

    class Edge:
        def __init__(self, u, v, cost):
            self.u, self.v, self.cost = u, v, cost

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

    def __init__(self, node_size):
        self._node = node_size
        self._edge_list = []

    def add_edge(self, u, v, cost):
        self._edge_list.append(self.Edge(u, v, cost))

    def solve(self):
        uf = UnionFind(self._node)
        res = 0
        edge_count = 0
        self._edge_list.sort()
        for e in self._edge_list:
            if not uf.same(e.u, e.v):
                uf.unite(e.u, e.v)
                res += e.cost
                edge_count += 1
                if edge_count == self._node-1:
                    break
        return res

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
    kr = Kruskal(n)
    for _ in range(m):
        s, t, w = map(int, sys.stdin.readline().split())
        kr.add_edge(s, t, w)
    print(kr.solve())

Submission status: Accepted

Solution code:
import sys


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

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

    def unite(self, ver1, ver2):
        ver1, ver2 = self.find(ver1), self.find(ver2)
        if ver1 == ver2:
            return
        if self.rank[ver1] < self.rank[ver2]:
            ver1, ver2 = ver2, ver1
        self.par[ver2] = ver1
        if self.rank[ver1] == self.rank[ver2]:
            self.rank[ver1] += 1

    def same(self, ver1, ver2):
        return self.find(ver1) == self.find(ver2)


class Kruskal:

    class Edge:
        def __init__(self, u, v, cost):
            self.u, self.v, self.cost = u, v, cost

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

    def __init__(self, node_size):
        self._node = node_size
        self._edge_list = []

    def add_edge(self, u, v, cost):
        self._edge_list.append(self.Edge(u, v, cost))

    def solve(self):
        uf = UnionFind(self._node)
        res = 0
        self._edge_list.sort()
        for e in self._edge_list:
            if not uf.same(e.u, e.v):
                uf.unite(e.u, e.v)
                res += e.cost
        return res

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
    kr = Kruskal(n)
    for _ in range(m):
        s, t, w = map(int, sys.stdin.readline().split())
        kr.add_edge(s, t, w)
    print(kr.solve())

Submission status: Accepted

Solution code:
import sys

def kruskal(n: int, edges: list) -> int:
    tree = [-1]*n

    def get_root(x):
        if tree[x] < 0:
            return x
        tree[x] = get_root(tree[x])
        return tree[x]

    def unite(x, y):
        x, y = get_root(x), get_root(y)
        if x != y:
            big, small = (x, y) if tree[x] < tree[y] else (y, x)
            tree[big] += tree[small]
            tree[small] = big
        return x != y

    return sum(w for (w, _, _), _ in zip(filter(lambda p: unite(p[1], p[2]), sorted(edges)), range(n-1)))

V, E = map(int, input().split())
edges = [(w, s, t) for s, t, w in (map(int, l.split()) for l in sys.stdin)]
print(kruskal(V, edges))

Submission status: Accepted

Solution code:
import sys

def kruskal(n: int, edges: list) -> int:
    tree = [-1]*n

    def get_root(x):
        if tree[x] < 0:
            return x
        tree[x] = get_root(tree[x])
        return tree[x]

    def unite(x, y):
        x, y = get_root(x), get_root(y)
        if x != y:
            big, small = (x, y) if tree[x] < tree[y] else (y, x)
            tree[big] += tree[small]
            tree[small] = big
        return x != y

    cost = 0
    for (w, _s, _t), _ in zip(filter(lambda p: unite(p[1], p[2]), sorted(edges)), range(n-1)):
        cost += w
    return cost

V, E = map(int, input().split())
edges = [(w, s, t) for s, t, w in (map(int, l.split()) for l in sys.stdin)]
print(kruskal(V, edges))

Submission status: Accepted

Solution code:
import sys

def kruskal(v_count: int, edges: list) -> int:
    tree = [-1]*v_count

    def get_root(x):
        if tree[x] < 0:
            return x
        tree[x] = get_root(tree[x])
        return tree[x]

    def unite(x, y):
        x, y = get_root(x), get_root(y)
        if x != y:
            big, small = (x, y) if tree[x] < tree[y] else (y, x)
            tree[big] += tree[small]
            tree[small] = big
        return x != y

    cost = 0
    for (w, _s, _t), _ in zip(filter(lambda p: unite(*p[1:]), sorted(edges)),
                              range(v_count-1)):
        cost += w
    return cost

V, E = map(int, input().split())
edges = [(w, s, t) for s, t, w in (map(int, l.split()) for l in sys.stdin)]
print(kruskal(V, edges))

Submission status: Accepted

Solution code:
import sys
from itertools import islice

def kruskal(v_count: int, edges: list) -> int:
    tree = [-1]*v_count

    def get_root(x):
        if tree[x] < 0:
            return x
        tree[x] = get_root(tree[x])
        return tree[x]

    def unite(a):
        x, y = get_root(a[1]), get_root(a[2])
        if x != y:
            big, small = (x, y) if tree[x] < tree[y] else (y, x)
            tree[big] += tree[small]
            tree[small] = big
        return x != y

    cost = 0
    for w, _s, _t in islice(filter(unite, sorted(edges)), v_count-1):
        cost += w
    return cost

V, E = map(int, input().split())
edges = [(w, s, t) for s, t, w in (map(int, l.split()) for l in sys.stdin)]
print(kruskal(V, edges))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        #親要素のノード番号を格納。par[x] == xのときそのノードはroot
        self.par = [i for i in range(n)]
        #木の高さ（初期状態では0）
        self.rank = [0] * n

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

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

    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
V, E = map(int, input().split())
nodes = sorted([list(map(int, input().split())) for _ in range(E)], key = lambda x: x[2])

a = UnionFind(V)
ans = 0
for node in nodes:
    si, ti = node[0] - 1, node[1] - 1
    if not a.same(si, ti):
        a.union(si, ti)
        ans += node[2]

print(ans)

Submission status: Accepted

Solution code:
from heapq import *

def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

N, M = map( int, input().split())
V = [ i for i in range(N)]
H = [(0,0,0)]*M
for i in range(M):
    s,t,w = map( int, input().split())
    H[i] = (w,s,t)
heapify(H)
ans = 0
while H:
    w,s,t = heappop(H)
    if find(V,s) != find(V,t):
        union(V,s,t)
        ans += w
print(ans)

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    def __init__(self, size):
        """
        size:頂点の数
        """
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]

    def find(self, x):
        """
        xのrootを返す
        """
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        """
        x,yを同じグループとしてまとめる
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

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

    def same(self, x, y):
        """
        xとyが同じグループならTrue
        """
        return self.find(x) == self.find(y)

    def component(self):
        """
        各連結成分のrootの集合を返す
        len()をとれば連結成分の数が求められる
        return-> set()
        """
        comp = set()
        for i in self.parent:
            p = self.find(i)
            comp.add(p)
        return comp

    def __str__(self):
        """
        for debug
        クラスのlistの情報を出力
        """
        ret = "parents\n"
        ret += " ".join(map(str, self.parent))
        ret += '\n'
        ret += " ".join(map(str, self.rank))
        return ret


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

Un = UnionFind(V)

edges = sorted(edges, key=lambda x: x[2])
cost = 0
for s, g, w in edges:
    if not Un.same(s, g):
        Un.union(s, g)
        cost += w
print(cost)

Submission status: Accepted

Solution code:
from sys import stdin

def read_edge(e):
    E = []
    for _ in range(e):
        line = stdin.readline().strip().split()
        u = line[0]
        v = line[1]
        w = line[2]
        E.append((int(w), int(u), int(v)))
    return E

class DisjointSet(object):
    def __init__(self, n):
        self.parent = [None] * (n + 1)
        self.rank = [None] * (n + 1)

    def make_set(self, x):
        if self.parent[x] == None:
            self.parent[x] = x
            self.rank[x] = 0

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

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

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

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

def kuruskal(n, E):
    S = DisjointSet(n)
    for i in range(n):
        S.make_set(i)
    K = []
    for i in sorted(E):
        if S.find_set(i[1]) != S.find_set(i[2]):
            S.unite(i[1], i[2])
            K.append(i[0])

    return K

n, e = [ int(i) for i in input().split() ]
E = read_edge(e)
K = kuruskal(n, E)
print(sum(K))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


import sys

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

# Union-Find木
class UnionFind:
    def __init__(self, n):
        self.n = n
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)
        # あるノードを根とする集合に属するノード数
        self.size = [1] * (n+1)
        # あるノードを根とする集合が木かどうか
        self.tree = [True] * (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 x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    # あるノードの属する集合のノード数
    def get_size(self, x):
        return self.size[self.find(x)]

    # 木かどうかの判定
    def is_tree(self, x):
        return self.tree[self.find(x)]

    # 集合の数
    def len(self):
        res = set()
        for i in range(self.n+1):
            res.add(self.find(i))
        # グループ0の分を引いて返却
        return len(res) - 1

N,M=MAP()
edges=[None]*M 
for i in range(M):
    s,t,w=MAP()
    edges[i]=(w, s, t)

# クラスカル法
edges.sort()
uf=UnionFind(N)
ans=0
for cost, u, v in edges:
    if not uf.same(u, v):
        uf.union(u, v)
        ans+=cost
print(ans)

Submission status: Accepted

Solution code:
import sys
import time
input = sys.stdin.readline

def find(tree,x):
    idx = tree[x][0]
    if(idx== x):
        return x
    else:
        root_idx = find(tree,idx)
        return root_idx

def unite(tree,x,y,w):
    x_root_idx = find(tree,x)
    y_root_idx = find(tree,y)

    if not (x_root_idx == y_root_idx):
        if(tree_rank[x_root_idx] < tree_rank[y_root_idx]):
            tree[x_root_idx] = (y_root_idx,w)
        else:
            tree[y_root_idx] = (x_root_idx,w)
            if(tree_rank[x_root_idx] == tree_rank[y_root_idx]):
                tree_rank[x_root_idx] = tree_rank[x_root_idx] + 1

def same(tree,x,y):
    x_root_idx = find(tree,x)
    y_root_idx = find(tree,y)
    if(x_root_idx == y_root_idx):
        return True
    else:
        return False

v_num,e_num = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(e_num)]
union_find_tree = [(i,0) for i in range(v_num)]
tree_rank = [0]*v_num
if __name__ == "__main__":
    edges.sort(key=lambda x:x[2])
    for e in edges:
        unite(union_find_tree,e[0],e[1],e[2])
    print(sum(item[1] for item in union_find_tree))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

line = input()
v, e = list(map(int, line.split()))
edge = {}
edge[0] = [[0, 0]]
for _ in range(0, e):
    line = input()
    s, t, w = list(map(int, line.split()))
    if s not in edge:
        edge[s]  = [[t, w]]
    else:
        edge[s] += [[t, w]]
    if t not in edge:
        edge[t]  = [[s, w]]
    else:
        edge[t] += [[s, w]]

def solve(v, edge):
    q = []
    vtx = set([i for i in range(0, v)])
    for t, w in edge[0]:
        heappush(q, (w, 0, t))
    vn = set([0])
    en = []
    cost = 0
    while len(vn) < v:
        w = s = t = 0
        qq = []
        while q:
            w, s, t = heappop(q)
            if s in vn and t not in vn:
                s, t = t, s
                break
            if s not in vn and t in vn:
                break
        vn.add(s)
        en += [(s, t)]
        cost += w
        for t, w in edge[s]:
            heappush(q, (w, s, t))
    return cost
        
print(solve(v, edge))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

weight.sort(key = lambda x: x[2])

parent = [i for i in range(V)]
rank = [0 for i in range(V)]

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

def union(x, y):
  a = find(x)
  b = find(y)
  if rank[a] < rank[b]:
    parent[a] = b
  else:
    parent[b] = a
    if rank[a] == rank[b]:
      rank[a] += 1
  

sum_weight = 0

for i in range(E):
  a, b, c = weight[i]
  if find(a) != find(b):
    union(a, b)
    sum_weight += c
  else:
    continue
  
print(sum_weight)

Submission status: Accepted

Solution code:
V=0
E=0
edge=[]
p=[]
rank=[]
answer=0
count=0

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] = rank[y] + 1
            
def findset(x):
    if x != p[x]:
        p[x] = findset(p[x])
    return p[x]
            
def takeThird(elem):
    return elem[2]
v,e = map(int,input().split())
V=v
E=e
while True:
    try:
        s,t,w = map(int,input().split())
    except:
        break
    else:
        edge.append([s,t,w])
        
edge.sort(key=takeThird)
for i in range(V):
    p.append(None)
    rank.append(None)
for i in range(V):
    makeset(i)
for i in range(len(edge)):
    if count == V-1:
        break
    if findset(edge[i][0]) == findset(edge[i][1]):
        continue
    union(edge[i][0],edge[i][1])
    answer+=edge[i][2]
    count+=1
    
print(answer)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

class UFSet:
    def __init__(self, n):
        self.fa = [i for i in range(n)]
        
    def find(self, v):
        if v != self.fa[v]:
            self.fa[v] = self.find(self.fa[v])
        return self.fa[v]
    
    def union(self, a, b):
        pa = self.find(a)
        pb = self.find(b)
        self.fa[pa] = pb
        

def kruscal(Edges, V):
    ufset = UFSet(V)
    ret = 0
    
    for w, a, b in Edges:
        pa, pb = ufset.find(a), ufset.find(b)
        if pa == pb:
            continue
        else:
            ret += w
            ufset.union(pa, pb)
    
    return ret
            
    
    
if __name__ == '__main__':
    line = sys.stdin.readline()
    V, E = line.split()
    V, E = int(V), int(E)
    
    Es = []
    
    for i in range(E):
        line = sys.stdin.readline()
        a, b, w = line.split()
        a, b, w = int(a), int(b), int(w)
        Es.append((w, a, b))
    
    Es.sort()
        
        
    sys.stdout.write(str(kruscal(Es, V)) + '\n')

Submission status: Accepted

Solution code:
def kruskal(g, size):
    g.sort(key=itemgetter(2), reverse=True)
    uf = union_find(size)
    tree = []
    while len(tree) < size - 1:
        u, v, d = g.pop()
        if not uf.union(u, v):
            tree.append((u, v, d))
    return tree

class union_find:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:return True
        
        if self.table[y] < self.table[x]:x, y = y, x

        self.table[x] += self.table[y]
        self.table[y] = x
        return False
            
    def find(self, x):
        if self.table[x] < 0:return x
        self.table[x] = self.find(self.table[x])
        return self.table[x]

from sys import stdin
from operator import itemgetter

import heapq

readline = stdin.readline


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

g = [list(map(int, readline().split())) for _ in range(e)]

tree = kruskal(g, v)

print(sum(d for s, t, d in tree))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
class Prim:
    """ find minimum spanning tree by Prim's algorithm
    """

    def __init__(self, V, E, start=0, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list (undirected graph)
            start: start vertex
            INF: Infinity cost
        """
        self.prim(V, E, start, INF)

    def prim(self, V, E, start=0, INF=10**9):
        used = [False] * V
        self.mincost = 0
        que = []
        heappush(que, (0, 0))
        while len(que) > 0:
            cost, v = heappop(que)
            if used[v]: continue
            used[v] = True
            self.mincost += cost
            for to, c in E[v]:
                heappush(que, (c, to))

    def minCost(self):
        return self.mincost
    

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

msp = Prim(V, edge)
print(msp.minCost())

Submission status: Accepted

Solution code:
class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       
       used in SRM505 div.2 900
    """
    def __init__(self, n):
        self.par = list(range(n)) # parent
        self.rank = [0] * n # depth of tree

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

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

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

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

class Kruskal:
    """ Kruskal's algorithm: find minimum spanning tree
        Complexity: O(E log(V))
        used in GRL2A(AOJ)
    """

    def __init__(self, V, E, start=0, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list (undirected graph)
        """
        self.kruskal(V, E)

    def kruskal(self, V, E):
        edges = []
        for v1 in range(V):
            for v2, cost in E[v1]:
                if v1 < v2: edges.append((cost, v1, v2))
        edges.sort()
        self.mincost = 0
        self.minSpanningTree = []
        uf = UnionFindTree(V)
        for cost, v1, v2 in edges:
            if uf.same(v1, v2) == False:
                self.mincost += cost
                uf.unite(v1, v2)
                self.minSpanningTree.append((v1, v2, cost))

    def minCost(self):
        return self.mincost

    def getMinSpanningTree(self):
        return sorted(self.minSpanningTree)
    
V, E = map(int, input().split())
edge = [[] for _ in range(V)]
for _ in range(E):
    s, t, w = map(int, input().split())
    edge[s].append((t, w))
    edge[t].append((s, w))

msp = Kruskal(V, edge)
print(msp.minCost())

Submission status: Accepted

Solution code:
class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       
       used in SRM505 div.2 900
    """
    def __init__(self, n):
        self.par = list(range(n)) # parent
        self.rank = [0] * n # depth of tree

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

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

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

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

class Kruskal:
    """ Kruskal's algorithm: find minimum spanning tree
        Complexity: O(E log(V))
        used in GRL2A(AOJ)
    """

    def __init__(self, V, E, start=0, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list (undirected graph)
        """
        self.kruskal(V, E)

    def kruskal(self, V, E):
        edges = []
        for v1 in range(V):
            for v2, cost in E[v1]:
                if v1 < v2: edges.append((cost, v1, v2))
        edges.sort(reverse=True)
        self.mincost = 0
        self.minSpanningTree = []
        uf = UnionFindTree(V)
        while len(self.minSpanningTree) < V - 1:
            cost, v1, v2 = edges.pop()
            if uf.same(v1, v2) == False:
                self.mincost += cost
                uf.unite(v1, v2)
                self.minSpanningTree.append((v1, v2, cost))

    def minCost(self):
        return self.mincost

    def getMinSpanningTree(self):
        return sorted(self.minSpanningTree)
    
V, E = map(int, input().split())
edge = [[] for _ in range(V)]
for _ in range(E):
    s, t, w = map(int, input().split())
    edge[s].append((t, w))
    edge[t].append((s, w))

msp = Kruskal(V, edge)
print(msp.minCost())

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.rank = [0] * size
        self.par = range(size)
        self.g_num = size

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

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

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

        self.g_num -= 1
        if (self.rank[x] > self.rank[y]):
            self.par[y] = x
        else:
            self.par[x] = y
            if (self.rank[x] == self.rank[y]): self.rank[y] += 1

    def group_num(self):
        return self.g_num



V, E = map(int, raw_input().split())
es = [map(int, raw_input().split()) for i in xrange(E)]
es.sort(key = lambda x: x[2])

uf = UnionFind(V)
ans = 0
for e in es:
    if not uf.same(e[0], e[1]):
        uf.unite(e[0], e[1])
        ans += e[2]
print ans

Submission status: Accepted

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

from collections import defaultdict
# クラスカル法を使う

V, E = map(int, input().split())
D = 0
tree = []
vertices = defaultdict(set)
for i in range(V):
    tree.append(i)          # 全ての頂点は自分の頂点 index と同じ index の木に属す
    vertices[i].add(i)

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

edges.sort(key=lambda x: x[2])
while edges:
    if V == 1:
        break
    s, t, d = edges.pop(0)
    if tree[s] != tree[t]:
        new = min(tree[s], tree[t])
        old = max(tree[s], tree[t])
        vertices[new] = vertices[new] | vertices[old]
        for vertex in vertices[old]:
            tree[vertex] = new

        D += d
        V -= 1
print(D)

Submission status: Accepted

Solution code:
from __future__ import division
from collections import defaultdict

class UFSet:
	def __init__(self, n):
		self.fa = [i for i in range(n + 1)]

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

	def union(self, x, y):
		fx = self.find(x)
		fy = self.find(y)
		if fx == fy:
			return fx
		else:
			self.fa[fx] = fy
			return fy


"""
graph is a hash
graph["nodes"] is a list of all nodes in the graph
graph["edges"] is a list of all edges in the graph in (x, y, w) form
  - x is the first nodes
  - y is the second nodes
  - w is the weight of the edges
graph["relation"] is the graph relation of the graph
"""

def kruscal(graph):
	"kruscal minimum spanning tree algorithm"
	n = len(graph["nodes"])
	ufset = UFSet(n)

	ret = 0

	for (x, y, w) in sorted(graph["edges"], key = lambda x: x[-1]):
		fx = ufset.find(x)
		fy = ufset.find(y)
		if fx != fy:
			ret += w
			ufset.union(fx, fy)
		else:
			pass
	return ret

if __name__ == '__main__':
	V, E = map(int, raw_input().strip().split())
	graph = {}
	graph["nodes"] = [i for i in range(V)]
	graph["edges"] = []
	graph["adj"] = defaultdict(list)
	for _ in range(E):
		x, y, w = map(int, raw_input().strip().split())
		graph["edges"].append((x, y, w))
		graph["adj"][x].append((y, w))
		graph["adj"][y].append((x, w))

	print kruscal(graph)