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|  s 0  t 0  w 0  s 1  t 1  w 1 : 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.  s i and t i represent source and target verticess of i -th edge (undirected) and w i 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 ≤ w i ≤ 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

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

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

Solution (Python):



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



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

Solution (Python):



import array
import collections
import heapq


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



def compute_mst_prim(max_v, adj_list):
    
    pred = collections.defaultdict(lambda: NO_VERTEX)
    
    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()

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

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

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

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

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

Solution (Python):


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








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

    def _find(self, x):
        if self.table[x] < 0:
            return x
        else:
            
            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]: 
                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




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)




kruskal(v_num, E)

Solution (Python):



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

Solution (Python):



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

Solution (Python):



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

Solution (Python):



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

Solution (Python):



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

Solution (Python):



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

Solution (Python):



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

Solution (Python):



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

Solution (Python):



"""
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
    
    edge_table.sort(key=attrgetter('weight'))
    
    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())

Solution (Python):



"""
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
from collections import namedtuple


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 graph_Kruskal():
    total_cost = 0
    
    edge_table.sort(key=attrgetter('cost'))
    
    case = UnionFind(size=vertices + 1)
    for edge in edge_table:
        if not case.same(edge.source, edge.target):
            total_cost += edge.cost
            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:])

    Edge = namedtuple('Edge', 'source target cost')
    edge_table = [Edge(source=int(s), target=int(t), cost=int(c)) for s, t, c in v_info]
    print(graph_Kruskal())

Solution (Python):
def find(x):
    if vertices[x] != x:
        vertices[x] = find(vertices[x])
    return vertices[x]

nv, ne = map(int, input().split(' '))
vertices = [i for i in range(nv)]
edges = []
for i in range(ne):
    s, t, w = map(int, input().split(' '))
    edges.append((s, t, w))

sum = 0
forest = [[v] for v in range(nv)]
edges.sort(key=lambda tup: tup[2])
for s, t, w in edges:
    u = find(s)
    v = find(t)
    if u != v:
        vertices[u] = v
        sum += w

print(sum)

Solution (Python):
def find(x):
    if parents[x] != x:
        parents[x] = find(parents[x])
    return parents[x]

nv, ne = map(int, input().split(' '))
parents = [i for i in range(nv)]
edges = []
for i in range(ne):
    s, t, w = map(int, input().split(' '))
    edges.append((s, t, w))

sum = 0
forest = [[v] for v in range(nv)]
edges.sort(key=lambda tup: tup[2])
for s, t, w in edges:
    u = find(s)
    v = find(t)
    if u != v:
        parents[u] = v
        sum += w

print(sum)

Solution (Python):
def find(x):
    if parents[x] != x:
        parents[x] = find(parents[x])
    return parents[x]

nv, ne = map(int, input().split(' '))
parents = [i for i in range(nv)]
edges = []
for i in range(ne):
    s, t, w = map(int, input().split(' '))
    edges.append((s, t, w))

sum = 0
edges.sort(key=lambda tup: tup[2])
for s, t, w in edges:
    u = find(s)
    v = find(t)
    if u != v:
        parents[u] = v
        sum += w

print(sum)

Solution (Python):
class UF:
    def __init__(self, n):
        self.N = n;
        self.d = [-1]*n
    
    def size(self, a):
        x = self.root(a)
        return -self.d[x]

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

    def unite(self, a, b):
        x = self.root(a)
        y = self.root(b)
        if self.size(x) < self.size(y):
            x, y = y, x
        self.d[y] = x
    
    def same(self, a, b):
        return self.root(a) == self.root(b)

class Edge:
    def __init__(self, f, t, w):
        self.f = f
        self.t = t
        self.w = w
    def __lt__(self, other):
        return self.w < other.w


def kruskal(edges, n):
    uf = UF(n)
    sum = 0
    for e in sorted(edges):
        if not uf.same(e.f, e.t):
            uf.unite(e.f, e.t)
            sum += e.w
    return sum


n, m = map(int, input().split())
es = []
for i in range(m):
    s, t, w = map(int, input().split())
    es.append(Edge(s, t, w))
print(kruskal(es, n))