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:
from __future__ import division
from collections import defaultdict

class UnionFindSet:
	def __init__(self, nodes):
		self.fa = {}
		for n in nodes:
			self.fa[n] = n

	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"
	ufset = UnionFindSet(graph["nodes"])

	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)

Submission status: Accepted

Solution code:
from collections import defaultdict
V, E = map(int, raw_input().split())
ans = 0
parent = [i for i in range(V)]
v = defaultdict(set)
for i in range(V):
    v[i].add(i)
edges = [map(int, raw_input().split()) for i in range(E)]
edges.sort(key = lambda x:x[2])
cnt = 0
while edges:
    if cnt == V - 1: break
    s, t, d = edges.pop(0)
    a, b = parent[s], parent[t]
    if a != b:
        if a > b: a, b = b, a
        v[a] = v[a] | v[b]
        for i in v[b]: parent[i] = a
        ans += d
        cnt += 1
print ans

Submission status: Accepted

Solution code:
import heapq
V,E=map(int, input().split())
nodes = [[] for i in range(V)]
cost = [[] for i in range(V)]
for i in range(E):
    s,t,w = map(int, input().split())
    nodes[s].append(t)
    cost[s].append(w)
    nodes[t].append(s)
    cost[t].append(w)

visited = [False] * V
total = 0
h = [(0,-1,0)]
while h:
    c,s,t = heapq.heappop(h)
    if visited[t]:
        continue
    total += c
    visited[t] = True
    for i in range(len(nodes[t])):
        nv = nodes[t][i]
        if not visited[nv]:
            heapq.heappush(h,(cost[t][i],t,nv))
print(total)

Submission status: Accepted

Solution code:
import heapq

nv, ne = map(int, input().split())

edges = [set() for _ in range(nv)]
while ne:
    s, t, w = map(int, input().split())
    edges[s].add((w, t))
    edges[t].add((w, s))
    ne -= 1

cost = 0
queue = list(edges[0])
heapq.heapify(queue)
visited = [False] * nv
visited[0] = True

while queue:
    edge_cost, t = heapq.heappop(queue)
    if visited[t]:
        continue
    visited[t] = True
    cost += edge_cost
    if all(visited):
        break
    for e in edges[t]:
        if not visited[e[1]]:
            heapq.heappush(queue, e)

print(cost)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
import collections


Edge = collections.namedtuple("Edge", "start end weight")


class UnionFind(object):

    def __init__(self, number_of_nodes):  # ?????????
        self.par = array.array("L", range(number_of_nodes))
        self.rank = array.array("L", (0 for i in range(number_of_nodes)))

    def root(self, node):  # ???????±???????
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r  # ????????§???
            return r

    def in_the_same_set(self, node1, node2):  # ????????????????±??????????
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):  # ?±??????????????????????
        x = self.root(node1)
        y = self.root(node2)
        if x == y:
            pass
        elif 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


# Kruskal????????????????°???¨?????¨????±???????
def compute_mst_kruskal(max_v, edges):
    edges.sort(key=lambda edge: edge.weight)
    uf = UnionFind(max_v)
    mst = []
    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


def main():
    max_v, max_e = map(int, input().split())
    edges = [Edge(*map(int, input().split())) for _ in range(max_e)]
    mst = compute_mst_kruskal(max_v, edges)
    print(sum(edge.weight for edge in mst))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
import collections
import heapq


AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
INF = 2 ** 31 - 1
NO_VERTEX = -1


# Prim?????§??????0?????????????°???¨?????¨????±???????
def compute_mst_prim(max_v, adj_list):
    # pred[u]?????????u???????????¨???????????????????????¨???
    pred = collections.defaultdict(lambda: NO_VERTEX)
    # u??¨pred[u]????????¶???????????????key[u]?????\???
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    # ??????????????????????????????????????\?????¨????????¨??????
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    # ????????????????????\?????????????????\??£???????????????????????????
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)


def main():
    max_v, max_e = map(int, input().split())
    adjacency_list = collections.defaultdict(set)
    for _ in range(max_e):
        s, t, w = map(int, input().split())
        adjacency_list[s].add(AdjacentVertex(t, w))
        adjacency_list[t].add(AdjacentVertex(s, w))
    (_, key) = compute_mst_prim(max_v, adjacency_list)
    print(sum(key.values()))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

V, E = map(int, raw_input().split())
parent = range(V)
def root(x):
    if parent[x] != x:
        x = parent[x] = root(parent[x])
    return x
def unite(x, y):
    rx = root(x); ry = root(y)
    if rx < ry:
        parent[ry] = rx
    else:
        parent[rx] = ry
def same(x, y):
    return root(x) == root(y)
que = []
for i in xrange(E):
    s, t, w = map(int, raw_input().split())
    heappush(que, (w, s, t))

ans = 0
while que:
    w, s, t = heappop(que)
    if not same(s, t):
        unite(s, t)
        ans += w
print ans

Submission status: Accepted

Solution code:
import heapq

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

  def find(self, x):
    while self.table[x] >= 0: x = self.table[x]
    return x

  def union(self, x, y):
    s1 = self.find(x)
    s2 = self.find(y)
    if s1 != s2:
      if self.table[s1] >= self.table[s2]:
        self.table[s1] += self.table[s2]
        self.table[s2] = s1
      else:
        self.table[s2] += self.table[s1]
        self.table[s1] = s2
      return True
    return False

def hash(n, s, g):
  return n*s+g

def dehash(n, hs):
  return [(hs-hs%n)/n, hs%n]

def kruskal(n, path):
  path = sorted(path.items(), key=lambda x:x[1])
  selected = {}
  union = UnionFind(n)
  for i in xrange(len(path)):
    k,v = path[i]
    s,g = dehash(n, k)
    if union.union(s, g):
      selected[k] = v
  return selected

def prim(n, path):
  selected = {}
  paths = []
  hq = []
  selected[0] = True

  if 0 not in path:
    return []

  for s,d,w in path[0]:
    heapq.heappush(hq, (w, [0,d,w]))

  while len(hq) != 0:
    k,root = heapq.heappop(hq)
    if root[1] in selected: continue
    selected[root[1]] = True
    paths.append(root)
    for s,d,w in path[root[1]]:
      heapq.heappush(hq, (w, [s,d,w]))
  return paths

V,E = map(int, raw_input().split())
path = {}
for _ in xrange(E):
  s,t,w = map(int, raw_input().split())
  if s not in path:
    path[s] = []
  path[s].append([s,t,w])
  if t not in path:
    path[t] = []
  path[t].append([t,s,w])
result = prim(V, path)
sumcost = 0
for s,d,v in result:
  sumcost += v
print sumcost

Submission status: Accepted

Solution code:
import heapq

def prim(n, path):
  selected = {}
  paths = []
  hq = []
  selected[0] = True

  if 0 not in path:
    return []

  for s,d,w in path[0]:
    heapq.heappush(hq, (w, [0,d,w]))

  while len(hq) != 0:
    k,root = heapq.heappop(hq)
    if root[1] in selected: continue
    selected[root[1]] = True
    paths.append(root)
    for s,d,w in path[root[1]]:
      heapq.heappush(hq, (w, [s,d,w]))
  return paths

V,E = map(int, raw_input().split())
path = {}
for _ in xrange(E):
  s,t,w = map(int, raw_input().split())
  if s not in path:
    path[s] = []
  path[s].append([s,t,w])
  if t not in path:
    path[t] = []
  path[t].append([t,s,w])
result = prim(V, path)
sumcost = 0
for s,d,v in result:
  sumcost += v
print sumcost

Submission status: Accepted

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

    def findset(self,x):
        if self.parent[x]==x:
            return x
        else:
            self.parent[x]=self.findset(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x=self.findset(x)
        y=self.findset(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):
        if self.findset(x)==self.findset(y):
            return True
        else:
            return False

def kruskal(n,m,edges):
    edges.sort()
    node=UnionFind(n)
    ret=0
    for i in xrange(m):
        cost,a,b=edges[i][0],edges[i][1],edges[i][2]
        if node.same(a,b):
            continue
        else:
            ret+=cost
            node.unite(a,b)
    return ret

n,m=map(int,raw_input().split())
edges=[]
for i in xrange(m):
    s,t,w=map(int,raw_input().split())
    edges.append([w,s,t])
print(kruskal(n,m,edges))

Submission status: Accepted

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

    def findset(self,x):
        if self.parent[x]==x:
            return x
        else:
            self.parent[x]=self.findset(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x=self.findset(x)
        y=self.findset(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):
        if self.findset(x)==self.findset(y):
            return True
        else:
            return False

def kruskal(v,e,edges):
    edges.sort()
    node=UnionFind(v)
    ret=0
    for i in xrange(e):
        cost,a,b=edges[i][0],edges[i][1],edges[i][2]
        if not node.same(a,b):
            ret+=cost
            node.unite(a,b)
    return ret

v,e=map(int,raw_input().split())
edges=[]
for i in xrange(e):
    s,t,w=map(int,raw_input().split())
    edges.append([w,s,t])
print(kruskal(v,e,edges))

Submission status: Accepted

Solution code:
# Acceptance of input

import sys

file_input = sys.stdin

v_num, e_num = map(int, file_input.readline().split())

E = []
for line in file_input:
    s, t, w = map(int, line.split())
    E.append((w, s, t))


# Disjoint Set: Union Find Tree

# Implementation of disjoint sets by tree
# Compression of the path
# merge smaller tree to large tree

class DisjointSets:
    def __init__(self, size):
        # negative values are roots(representatives of each tree)
        # positive values represent the parent element
        self.table = [-1 for _ in range(size)]

    def _find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # compression of the path
            self.table[x] = self._find(self.table[x])
            return self.table[x]

    def uniteSets(self, x, y):
        s1 = self._find(x)
        s2 = self._find(y)
        if s1 != s2:
            if self.table[s1] < self.table[s2]: # the smaller has more elements
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2

    def isDisjoint(self, x, y):
        if self._find(x) != self._find(y):
            return True
        else:
            return False


# Kruskal's algorithm

def kruskal(vertices_num, edges):
    edges.sort(reverse = True)
    S = DisjointSets(vertices_num)
    weight = 0

    while edges:
        w, s, t = edges.pop()
        if S.isDisjoint(s, t):
            S.uniteSets(s, t)
            weight += w

    print(weight)


# Output

kruskal(v_num, E)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
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

output:
5
"""

import sys
import heapq as hp

WHITE, GRAY, BLACK = 0, 1, 2


def generate_adj_table(v_table):
    for each in v_table:
        v_from, v_to, edge_weight = map(int, each)
        init_adj_table[v_from][v_to] = edge_weight
        init_adj_table[v_to][v_from] = edge_weight

    return init_adj_table


def prim_span_tree():
    distance[init_v] = 0
    parent[init_v] = -1
    path_heap = []
    hp.heappush(path_heap, (distance[init_v], init_v))

    while len(path_heap) >= 1:
        current_vertex = hp.heappop(path_heap)[1]

        color[current_vertex] = BLACK

        for adj_vertex, adj_weight in adj_table[current_vertex].items():
            if color[adj_vertex] is not BLACK:
                if adj_weight < distance[adj_vertex]:
                    distance[adj_vertex] = adj_weight
                    parent[adj_vertex] = current_vertex
                    color[adj_vertex] = GRAY
                    hp.heappush(path_heap, (distance[adj_vertex], adj_vertex))

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    parent = [-1] * vertices
    distance = [float('inf')] * vertices
    color = [WHITE] * vertices
    init_v = 0

    init_adj_table = tuple(dict() for _ in range(vertices))
    adj_table = generate_adj_table(v_info)
    print(sum(prim_span_tree()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
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

output:
5
"""

import sys
import heapq as hp

WHITE, GRAY, BLACK = 0, 1, 2


def generate_adj_table(v_table):
    for each in v_table:
        v_from, v_to, edge_weight = map(int, each)
        init_adj_table[v_from][v_to] = edge_weight
        init_adj_table[v_to][v_from] = edge_weight

    return init_adj_table


def prim_span_tree():
    distance[init_v] = 0
    parent[init_v] = -1
    path_heap = []
    hp.heappush(path_heap, (distance[init_v], init_v))

    while len(path_heap) >= 1:
        current_vertex = hp.heappop(path_heap)[1]

        color[current_vertex] = BLACK

        for adj_vertex, adj_weight in adj_table[current_vertex].items():
            if color[adj_vertex] is not BLACK:
                if adj_weight < distance[adj_vertex]:
                    distance[adj_vertex] = adj_weight
                    parent[adj_vertex] = current_vertex
                    color[adj_vertex] = GRAY
                    hp.heappush(path_heap, (adj_weight, adj_vertex))

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    parent = [-1] * vertices
    distance = [float('inf')] * vertices
    color = [WHITE] * vertices
    init_v = 0

    init_adj_table = tuple(dict() for _ in range(vertices))
    adj_table = generate_adj_table(v_info)
    print(sum(prim_span_tree()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
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

output:
5
"""

import sys
import heapq as hp

WHITE, GRAY, BLACK = 0, 1, 2


def generate_adj_table(v_table):
    for each in v_table:
        v_from, v_to, edge_weight = map(int, each)
        init_adj_table[v_from][v_to] = edge_weight
        init_adj_table[v_to][v_from] = edge_weight

    return init_adj_table


def prim_span_tree():
    distance[init_v] = 0
    parent[init_v] = -1
    path_heap = []
    hp.heappush(path_heap, (0, init_v))

    while len(path_heap) >= 1:
        current_vertex = hp.heappop(path_heap)[1]

        color[current_vertex] = BLACK

        for adj_vertex, adj_weight in adj_table[current_vertex].items():
            if color[adj_vertex] is not BLACK:
                if adj_weight < distance[adj_vertex]:
                    distance[adj_vertex] = adj_weight
                    parent[adj_vertex] = current_vertex
                    color[adj_vertex] = GRAY
                    hp.heappush(path_heap, (adj_weight, adj_vertex))

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    parent = [-1] * vertices
    distance = [float('inf')] * vertices
    color = [WHITE] * vertices
    init_v = 0

    init_adj_table = tuple(dict() for _ in range(vertices))
    adj_table = generate_adj_table(v_info)
    print(sum(prim_span_tree()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
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

output:
5
"""

import sys
import heapq as hp

WHITE, GRAY, BLACK = 0, 1, 2


def generate_adj_table(v_table):
    for each in v_table:
        v_from, v_to, edge_weight = map(int, each)
        init_adj_table[v_from][v_to] = edge_weight
        init_adj_table[v_to][v_from] = edge_weight

    return init_adj_table


def prim_span_tree():
    distance[init_v] = 0
    parent[init_v] = -1
    distance_heap = []
    hp.heappush(distance_heap, (0, init_v))

    while distance_heap:
        current_vertex = hp.heappop(distance_heap)[1]

        color[current_vertex] = BLACK

        for adj_vertex, adj_weight in adj_table[current_vertex].items():
            if color[adj_vertex] is not BLACK:
                if adj_weight < distance[adj_vertex]:
                    distance[adj_vertex] = adj_weight
                    parent[adj_vertex] = current_vertex
                    color[adj_vertex] = GRAY
                    hp.heappush(distance_heap, (adj_weight, adj_vertex))

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    parent = [-1] * vertices
    distance = [float('inf')] * vertices
    color = [WHITE] * vertices
    init_v = 0

    init_adj_table = tuple(dict() for _ in range(vertices))
    adj_table = generate_adj_table(v_info)
    print(sum(prim_span_tree()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
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

output:
5
"""

import sys
import heapq as hp
from operator import attrgetter


class Edge(object):
    __slots__ = ('source', 'target', 'weight')

    def __init__(self):
        self.weight = float('inf')
        self.source, self.target = None, None


class UnionFind(object):
    __slots__ = ('size', 'tree_height_rank_list', 'ancestor_list')

    def __init__(self, size):
        self.size = int(size)
        self.tree_height_rank_list = [0] * self.size
        self.ancestor_list = [i for i in range(self.size)]

    def _find(self, x):
        if x != self.ancestor_list[x]:
            self.ancestor_list[x] = self._find(self.ancestor_list[x])
        return self.ancestor_list[x]

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

    def _link(self, x, y):
        if self.tree_height_rank_list[x] > self.tree_height_rank_list[y]:
            self.ancestor_list[y] = x
        else:
            self.ancestor_list[x] = y
            if self.tree_height_rank_list[x] == self.tree_height_rank_list[y]:
                self.tree_height_rank_list[y] += 1

    def union(self, x, y):
        self._link(self._find(x), self._find(y))


def generate_edge_table(v_table):
    for index, each in enumerate(v_table):
        source, target, weight = map(int, each)
        init_edge_table[index].source = source
        init_edge_table[index].target = target
        init_edge_table[index].weight = weight

    return init_edge_table


def graph_Kruskal():
    total_cost = 0
    edge_table.sort(key=attrgetter('weight'))
    # print([i.weight for i in edge_table])
    union_find_case = UnionFind(size=vertices + 1)
    for edge in edge_table:
        if not union_find_case.same(edge.source, edge.target):
            total_cost += edge.weight
            union_find_case.union(edge.source, edge.target)

    return total_cost


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    init_edge_table = [Edge() for _ in range(edges)]
    edge_table = generate_edge_table(v_info)
    print(graph_Kruskal())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
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

output:
5
"""

import sys
from operator import attrgetter


class Edge(object):
    __slots__ = ('source', 'target', 'weight')

    def __init__(self):
        self.weight = float('inf')
        self.source, self.target = None, None


class UnionFind(object):
    __slots__ = ('size', 'tree_height_rank_list', 'ancestor_list')

    def __init__(self, size):
        self.size = int(size)
        self.tree_height_rank_list = [0] * self.size
        self.ancestor_list = [i for i in range(self.size)]

    def _find(self, x):
        if x != self.ancestor_list[x]:
            self.ancestor_list[x] = self._find(self.ancestor_list[x])
        return self.ancestor_list[x]

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

    def _link(self, x, y):
        if self.tree_height_rank_list[x] > self.tree_height_rank_list[y]:
            self.ancestor_list[y] = x
        else:
            self.ancestor_list[x] = y
            if self.tree_height_rank_list[x] == self.tree_height_rank_list[y]:
                self.tree_height_rank_list[y] += 1

    def union(self, x, y):
        self._link(self._find(x), self._find(y))


def generate_edge_table(v_table):
    for index, each in enumerate(v_table):
        source, target, weight = map(int, each)
        init_edge_table[index].source = source
        init_edge_table[index].target = target
        init_edge_table[index].weight = weight

    return init_edge_table


def graph_Kruskal():
    total_cost = 0
    edge_table.sort(key=attrgetter('weight'))
    # MST--> E = V + 1
    union_find_case = UnionFind(size=vertices + 1)
    for edge in edge_table:
        if not union_find_case.same(edge.source, edge.target):
            total_cost += edge.weight
            union_find_case.union(edge.source, edge.target)

    return total_cost


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    init_edge_table = [Edge() for _ in range(edges)]
    edge_table = generate_edge_table(v_info)
    print(graph_Kruskal())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
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

output:
5
"""

import sys
import heapq as hp

WHITE, GRAY, BLACK = 0, 1, 2


def generate_adj_table(v_table):
    for each in v_table:
        v_from, v_to, edge_weight = map(int, each)
        init_adj_table[v_from][v_to] = edge_weight
        init_adj_table[v_to][v_from] = edge_weight

    return init_adj_table


def prim_span_tree():
    distance[init_v] = 0
    distance_heap = []
    hp.heappush(distance_heap, (0, init_v))

    while distance_heap:
        current_vertex = hp.heappop(distance_heap)[1]

        color[current_vertex] = BLACK

        for adj_vertex, adj_weight in adj_table[current_vertex].items():
            if color[adj_vertex] is not BLACK:
                if adj_weight < distance[adj_vertex]:
                    distance[adj_vertex] = adj_weight
                    parent[adj_vertex] = current_vertex
                    color[adj_vertex] = GRAY
                    hp.heappush(distance_heap, (adj_weight, adj_vertex))

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    parent = [-1] * vertices
    distance = [float('inf')] * vertices
    color = [WHITE] * vertices
    init_v = 0

    init_adj_table = tuple(dict() for _ in range(vertices))
    adj_table = generate_adj_table(v_info)
    print(sum(prim_span_tree()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
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

output:
5
"""

import sys
from operator import attrgetter


class Edge(object):
    __slots__ = ('source', 'target', 'weight')

    def __init__(self):
        self.weight = float('inf')
        self.source, self.target = None, None


class UnionFind(object):
    __slots__ = ('size', 'tree_height_rank_list', 'ancestor_list')

    def __init__(self, size):
        self.size = int(size)
        self.tree_height_rank_list = [0] * self.size
        self.ancestor_list = [i for i in range(self.size)]

    def _find(self, x):
        if x != self.ancestor_list[x]:
            self.ancestor_list[x] = self._find(self.ancestor_list[x])
        return self.ancestor_list[x]

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

    def _link(self, x, y):
        if self.tree_height_rank_list[x] > self.tree_height_rank_list[y]:
            self.ancestor_list[y] = x
        else:
            self.ancestor_list[x] = y
            if self.tree_height_rank_list[x] == self.tree_height_rank_list[y]:
                self.tree_height_rank_list[y] += 1

    def union(self, x, y):
        self._link(self._find(x), self._find(y))


def generate_edge_table(v_table):
    for index, each in enumerate(v_table):
        source, target, weight = map(int, each)
        init_edge_table[index].source = source
        init_edge_table[index].target = target
        init_edge_table[index].weight = weight

    return init_edge_table


def graph_Kruskal():
    total_cost = 0
    # sort edge_table by edge's weight
    edge_table.sort(key=attrgetter('weight'))
    # MST--> E = V + 1
    union_find_case = UnionFind(size=vertices + 1)
    for edge in edge_table:
        if not union_find_case.same(edge.source, edge.target):
            total_cost += edge.weight
            union_find_case.union(edge.source, edge.target)

    return total_cost


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    init_edge_table = [Edge() for _ in range(edges)]
    edge_table = generate_edge_table(v_info)
    print(graph_Kruskal())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
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

output:
5
"""

import sys
from operator import attrgetter


class Edge(object):
    __slots__ = ('source', 'target', 'weight')

    def __init__(self):
        self.weight = float('inf')
        self.source, self.target = None, None


class UnionFind(object):
    __slots__ = ('size', 'tree_height_rank', 'ancestors')

    def __init__(self, size):
        self.size = int(size)
        self.tree_height_rank = [0] * self.size
        self.ancestors = [i for i in range(self.size)]

    def _find(self, x):
        if x != self.ancestors[x]:
            self.ancestors[x] = self._find(self.ancestors[x])
        return self.ancestors[x]

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

    def _link(self, x, y):
        if self.tree_height_rank[x] > self.tree_height_rank[y]:
            self.ancestors[y] = x
        else:
            self.ancestors[x] = y
            if self.tree_height_rank[x] == self.tree_height_rank[y]:
                self.tree_height_rank[y] += 1

    def union(self, x, y):
        self._link(self._find(x), self._find(y))


def generate_edge_table(v_table):
    for index, each in enumerate(v_table):
        source, target, weight = map(int, each)
        edge = init_edge_table[index]
        edge.source = source
        edge.target = target
        edge.weight = weight

    return init_edge_table


def graph_Kruskal():
    total_cost = 0
    # sort edge_table by edge's weight
    edge_table.sort(key=attrgetter('weight'))
    # MST--> E = V + 1
    union_find_case = UnionFind(size=vertices + 1)
    for edge in edge_table:
        if not union_find_case.same(edge.source, edge.target):
            total_cost += edge.weight
            union_find_case.union(edge.source, edge.target)

    return total_cost


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    init_edge_table = [Edge() for _ in range(edges)]
    edge_table = generate_edge_table(v_info)
    print(graph_Kruskal())