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:
#!/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
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
    # sort edge_table by edge's weight
    edge_table.sort(key=attrgetter('cost'))
    # MST--> E = V + 1
    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())

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class UnionFindTree:
    def __init__(self, V):
        self.parent = [i for i in range(V)]

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

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        self.parent[rx] = ry
        return

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

class Edge:
    def __init__(self, s, t, w):
        self.s = s
        self.t = t
        self.w = w

    def __lt__(self, right):
        return self.w < right.w

def Kruscal(edges, V):
    utf = UnionFindTree(V)
    res = 0
    edges.sort()
    for e in edges:
        s = e.s
        t = e.t
        if not utf.find(e.s, e.t):
            res += e.w
            utf.unite(e.s, e.t)
    return res

def main():
    [V, E] = map(int, (raw_input()).split(" "))
    edges = [None]*E
    for i in range(E):
        [s,t,w] = map(int, (raw_input()).split(" "))
        edges[i] = Edge(s,t,w)

    print Kruscal(edges, V)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

vertices,edges = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
way = [float("inf")] * vertices
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 = [0] * vertices
now_weight = 0
way[0] = 0

while queue:
    here_weight,here = heapq.heappop(queue)
    #print(went)
    if went[here]:
        continue
    went[here] = 1
    now_weight += here_weight
    min_weight,next_t = float("inf"),-1
    for c in link[here]:
        if not went[c] and way[c] > weight[here][c]:
            heapq.heappush(queue,[weight[here][c],c])
            way[c] = weight[here][c]
    #print(queue)
print(now_weight)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

def solve():
    n, m = map(int, sys.stdin.readline().split())
    edges = [None] * m

    for i in range(m):
        s, t, w = map(int, sys.stdin.readline().split())
        edges[i] = (s, t, w)

    edges.sort(key=itemgetter(2), reverse=True)

    uf = UnionFind(n)

    ans = 0

    for i in range(n - 1):
        while edges:
            s, t, w = edges.pop()

            if not uf.same(s, t):
                uf.unite(s, t)
                break

        ans += w

    print(ans)

class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.rank = [0] * n

    def find_root(self, x):
        if x != self.p[x]:
            self.p[x] = self.find_root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
        else:
            self.p[v] = u

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import heapq as pq
n,E = map(int, input().split())
M = [[] for i in range(n)]
for i in range(E):
 s,t,w = map(int, input().split())
 M[s].append([t,w])
 M[t].append([s,w])

def prim():
 color = [0] * n
 d = [float("inf")] * n
 d[0] = 0
 H = []
 pq.heappush(H, [0, 0])
 while H:
  u2,u1 = pq.heappop(H)
  color[u1] = 1
  if d[u1] < u2: continue
  for v1, v2 in M[u1]:
   if color[v1] == 1: continue
   if d[v1] > v2:
    d[v1] = v2
    pq.heappush(H, [d[v1], v1])
 return sum(d)
 
print(prim())

Submission status: Accepted

Solution code:
import sys


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.p = [i for i in range(n + 5)]
        self.rank = [0 for i in range(n + 5)]

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

    def unite(self, x, y):
        px, py = self.find_set(x), self.find_set(y)
        if px == py:
            return
        if self.rank[px] > self.rank[py]:
            self.p[py] = px
        else:
            self.p[px] = py
            if self.rank[px] == self.rank[py]:
                self.rank[py] += 1


def main():
    sys.setrecursionlimit(int(1e5))
    nvertices, nedges = map(int, input().split())
    E = []
    uf = UnionFind(nvertices)
    for i in range(nedges):
        s, t, w = map(int, input().split())
        E.append((w, s, t))
    E.sort()

    ans = 0
    for w, s, t in E:
        if uf.find_set(s) != uf.find_set(t):
            ans += w
            uf.unite(s, t)

    print(ans)


main()

Submission status: Accepted

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


class UnionFind:
    __slots__ = ["nodes"]

    def __init__(self, n: int) -> None:
        self.nodes = [-1]*n

    def get_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> bool:
        root_x, root_y = self.get_root(x), self.get_root(y)
        if root_x != root_y:
            bigroot, smallroot = \
                (root_x, root_y) if self.nodes[root_x] < self.nodes[root_y] else (root_y, root_x)
            self.nodes[bigroot] += self.nodes[smallroot]
            self.nodes[smallroot] = bigroot
            return True
        else:
            return False


def kruskal(n: int, edges: list) -> int:
    edges.sort()
    tree = UnionFind(n)
    total = 0
    cnt = 0
    for w, s, t in edges:
        if tree.unite(s, t):
            cnt += 1
            total += w
            if cnt == n - 1:
                break

    return total


V, E = map(int, readline().split())
edges = []
append = edges.append
for _ in [None]*E:
    s, t, w = map(int, readline().split())
    append((w, s, t))
print(kruskal(V, edges))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from operator import itemgetter
class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.rank = [0] * n
    def find_root(self, x):
        if x != self.p[x]:
            self.p[x] = self.find_root(self.p[x])
        return self.p[x]
    def same(self, x, y):
        return self.find_root(x) == self.find_root(y)
    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)
        if u == v: return
        if self.rank[u] < self.rank[v]:
            self.p[u] = v
        else:
            self.p[v] = u
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1
n, m = map(int, readline().split())
edges = []
for _ in [0] * (m):
    s, t, w = map(int, readline().split())
    edges.append((s, t, w))
edges.sort(key=itemgetter(2), reverse=True)
uf = UnionFind(n)
ans = 0
for _ in [0] * (n - 1):
    while edges:
        s, t, w = edges.pop()
        if not uf.same(s, t):
            uf.unite(s, t)
            break
    ans += w
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from operator import itemgetter
class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.rank = [0] * n
    def find_root(self, x):
        if x != self.p[x]:
            self.p[x] = self.find_root(self.p[x])
        return self.p[x]
    def same(self, x, y):
        return self.find_root(x) == self.find_root(y)
    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)
        if u == v: return
        if self.rank[u] < self.rank[v]:
            self.p[u] = v
        else:
            self.p[v] = u
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1
n, m = map(int, readline().split())
edges = [None] * m
for i in range(m):
    s, t, w = map(int, readline().split())
    edges[i] = (s, t, w)
edges.sort(key=itemgetter(2), reverse=True)
uf = UnionFind(n)
ans = 0
for _ in [0] * (n - 1):
    while edges:
        s, t, w = edges.pop()
        if not uf.same(s, t):
            uf.unite(s, t)
            break
    ans += w
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from operator import itemgetter
class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.rank = [0] * n
    def find_root(self, x):
        if x != self.p[x]:
            self.p[x] = self.find_root(self.p[x])
        return self.p[x]
    def same(self, x, y):
        return self.find_root(x) == self.find_root(y)
    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)
        if u == v: return
        if self.rank[u] < self.rank[v]:
            self.p[u] = v
        else:
            self.p[v] = u
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1
n, m = map(int, readline().split())
edges = [tuple(map(int, readline().split())) for _ in [0] * m]
edges.sort(key=itemgetter(2), reverse=True)
uf = UnionFind(n)
ans = 0
for _ in [0] * (n - 1):
    while edges:
        s, t, w = edges.pop()
        if not uf.same(s, t):
            uf.unite(s, t)
            break
    ans += w
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from operator import itemgetter
class UnionFind:
    __slots__ = ['p', 'rank']
    def __init__(self, n):
        self.p = list(range(n))
        self.rank = [0] * n
    def find_root(self, x):
        if x != self.p[x]:
            self.p[x] = self.find_root(self.p[x])
        return self.p[x]
    def same(self, x, y):
        return self.find_root(x) == self.find_root(y)
    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)
        if u == v: return
        if self.rank[u] < self.rank[v]:
            self.p[u] = v
        else:
            self.p[v] = u
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1
n, m = map(int, readline().split())
edges = [tuple(map(int, readline().split())) for _ in [0] * m]
edges.sort(key=itemgetter(2), reverse=True)
uf = UnionFind(n)
ans = 0
for _ in [0] * (n - 1):
    while edges:
        s, t, w = edges.pop()
        if not uf.same(s, t):
            uf.unite(s, t)
            break
    ans += w
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys


class UnionFind:

    def __init__(self, nvertices):
        self.rank = [1] * (nvertices + 5)
        self.p = [i for i in range(nvertices + 5)]

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])
        return self.p[u]

    def unite(self, u, v):
        x = self.find_set(u)
        y = self.find_set(v)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def is_connected(self, u, v):
        return self.find_set(u) == self.find_set(v)


def main():
    sys.setrecursionlimit(int(1e5))
    nvertices, nedges = map(int, input().split())
    edges = []
    for i in range(nedges):
        u, v, w = map(int, input().split())
        edges.append((w, u, v))

    edges.sort(key=lambda e: e[0])
    ans = 0
    uf = UnionFind(nvertices)
    for w, u, v in edges:
        if not uf.is_connected(u, v):
            uf.unite(u, v)
            ans += w

    print(ans)


main()

Submission status: Accepted

Solution code:
import heapq


def main():
    nvertices, nedges = map(int, input().split())
    Adj = [[] for i in range(nvertices)]
    for i in range(nedges):
        u, v, w = map(int, input().split())
        Adj[u].append((v, w))
        Adj[v].append((u, w))

    INF = float('inf')
    Q = [(0, 0)]
    for i in range(1, nvertices):
        Q.append((INF, i))
    heapq.heapify(Q)
    key = [INF] * nvertices
    key[0] = 0
    done = [False] * nvertices
    ans = 0
    while Q:
        val, u = heapq.heappop(Q)
        if val > key[u]:
            continue
        done[u] = True
        ans += val
        for v, w in Adj[u]:
            if not done[v] and w < key[v]:
                key[v] = w
                heapq.heappush(Q, (w, v))

    print(ans)


main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappush, heappop
INF = 9999999999999999999999999999

def spanning_tree(G):
  n = len(G)
  T = {}
  added = set([0])
  heap = []
  for v in G[0]:
    heappush(heap, (G[0][v], (0, v)))
  while len(added) < n:
    while True:
      c, e = heappop(heap)
      if e[1] not in added:
        break
    T[e] = c
    added.add(e[1])
    for v in G[e[1]]:
      heappush(heap, (G[e[1]][v], (e[1], v)))

  return T


G = {}

n, m = [int(v) for v in input().strip().split(' ')]
for i in range(n):
  G[i] = {}
for _ in range(m):
  s, t, c = [int(v) for v in input().strip().split(' ')]
  G[s][t] = c
  G[t][s] = c

if m == 0:
  print(0)
  exit()

T = spanning_tree(G)

s = 0
for e in T:
  s += T[e]

print(s)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

INF = float('inf')


V, E = map(int, input().split())
Adj_list = defaultdict(set)

for i in range(E):
    s, t, w = map(int, input().split())
    Adj_list[s].add((t, w))
    Adj_list[t].add((s, w))
    
def prim(x):
    d = [INF] * x
    d[0] = 0
    isVisited = [False] * x
    hq = [(0,0)] 
    
    while hq:
        u = heapq.heappop(hq)[1]
        isVisited[u] = True
        
        for v, c in Adj_list[u]:
            if not isVisited[v] and d[v] > c:
                d[v] = c
                heapq.heappush(hq, (c, v))
    return sum(d)

print(prim(V))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp

"""
import sys
from sys import stdin
input = stdin.readline
from collections import namedtuple


class DisjointSet(object):
    def __init__(self, size):
        self.rank = []
        self.p = []
        for i in range(size):
            self.makeSet(i)

    def makeSet(self, x):
        self.p.insert(x, x)
        self.rank.insert(x, 0)

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

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

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

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



def kruskal(V, E, es):
    es.sort(key=lambda x: x.c)
    uf = DisjointSet(V)
    res = 0

    for i in range(E):
        e = es[i]
        if not uf.same(e.u, e.v):
            uf.unite(e.u, e.v)
            res += e.c
    return res

edge = namedtuple('edge', ['u', 'v', 'c'])
def main(args):
    V, E = map(int, input().split())
    es = []
    for _ in range(E):
        s, t, w = map(int, input().split())
        es.append(edge(s, t, w))

    result = kruskal(V, E, es)
    print(result)



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from operator import itemgetter

import sys
sys.setrecursionlimit(10000)

def inpl(): return tuple(map(int, input().split()))

V, E = inpl()
edges = []
graph = [[] for _ in range(V)]  # [target, cost]
total_cost = 0

for _ in range(E):
    edges.append(inpl())

gw = itemgetter(2)
edges = sorted(edges, key = gw)

tree = [[-1, 1]  for _ in range(V)] # [next, rank]

def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0])    
    return group
 
def unite(x, y):
    px = find(x)
    py = find(y)
     
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
 
for s, t, w in edges:
    if find(s) != find(t):
        unite(s, t)
        total_cost += w
        graph[s].append([t, w])
        graph[t].append([s, w])

print(total_cost)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq
vertices, edges = (int(n) for n in input().split(" "))
conn = defaultdict(set)
weight = defaultdict(dict)
for i in range(edges):
    v1, v2, w = (int(n) for n in input().split(" "))
    conn[v1] |= {v2}
    conn[v2] |= {v1}
    weight[v1][v2] = w
    weight[v2][v1] = w

queue = []
heapq.heapify(queue)
heapq.heappush(queue, [0,0])
went = set()
went_vertices = 0
answer_weight = 0
while went_vertices < vertices:
    here_weight, here_v = heapq.heappop(queue)
    if here_v in went:
        continue
    went |= {here_v}
    for c in conn[here_v]:
        if c not in went:
            heapq.heappush(queue,[weight[here_v][c], c])
    answer_weight += here_weight
    went_vertices += 1
print(answer_weight)

Submission status: Accepted

Solution code:
rank = {}
p = {}

class Edge: pass

def makeSet(x):
    p[x] = x
    rank[x] = 0
 
def link(x, y):
    if  rank[x] > rank[y]: p[y] = x
    else: p[x] = y
    if  rank[x] == rank[y]:
        rank[y] += 1
 
def union(x, y):
    link(findSet(x), findSet(y))
     
def findSet(x):
    if  x != p[x]: p[x] = findSet(p[x])
    return p[x]
     
def isSameSet(x, y):
    return findSet(x) == findSet(y)
 
V, E = map(int, input().split())
el = []

for i in range(E):
    s,t,w = map(int, input().split())
    e=Edge()
    e.source = s
    e.target = t
    e.weight = w
    el.append(e)

def kruskal(v, e):
    e = sorted(e, key=lambda x: x.weight)
    for i in v:
        makeSet(i)
    K = []
    for i in e:
        if findSet(i.source) != findSet(i.target):
            union(i.source, i.target)
            K.append(i.weight)
    return K

print(sum(kruskal(range(V), el)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from operator import itemgetter


class DisjointSet():
    def __init__(self, size):
        self.size = size
        self.rank = [None] * size
        self.parents = [None] * size
        for i in range(size):
            self.makeSet(i)

    def makeSet(self, x):
        self.parents[x] = x
        self.rank[x] = 0

    def findSet(self, x):
        if x != self.parents[x]:
            self.parents[x] = self.findSet(self.parents[x])
        return self.parents[x]

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

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

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


if __name__ == '__main__':

    n, m = [int(s) for s in input().split()]
    E = []
    for _ in range(m):
        E.append([int(s) for s in input().split(" ")])

    def kruskal(n, E):
        E = sorted(E, key=itemgetter(2))
        totalCost = 0
        S = DisjointSet(n)
        # K = []

        for s, t, w in E:
            if S.findSet(s) != S.findSet(t):
                S.unite(s, t)
                # K.append([s,t,w])
                totalCost += w

        return totalCost

    print(kruskal(n, E))

Submission status: Accepted

Solution code:
import array, 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 _ 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(v_size, edges):
    edges.sort(key=lambda e: e.weight)
    uf = UnionFind(v_size)
    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


edges = []
v, e = map(int, input().split())
for _ in range(e):
  edges.append(Edge(*map(int, input().split())))
print(sum(e.weight for e in compute_mst_kruskal(v, edges)))

Submission status: Accepted

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

from collections import deque

q = deque(sorted(data, key=lambda x: x[2]))


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

# Union-Find  ---------------
def find(x):
    if parent[x] == x:
        return x
    else:
        parent[x] = find(parent[x])
        return parent[x]

def judge(a, b):
    a_parent = find(a)
    b_parent = find(b)
    if a_parent == b_parent:
        return True
    else:
        return False

def merge(a, b):
    a_parent = find(a)
    b_parent = find(b)
    if a_parent == b_parent:
        return
    else:
        if rank[a_parent] > rank[b_parent]:
            parent[b_parent] = a_parent
        elif rank[a_parent] < rank[b_parent]:
            parent[a_parent] = b_parent
        else:
            parent[a_parent] = b_parent
            rank[b_parent] += 1

#----------------------------


ans = 0
while len(q) > 0:
    a = q.popleft()
    if not judge(a[0], a[1]):
        merge(a[0], a[1])
        ans += a[2]

print(ans)

Submission status: Accepted

Solution code:
import sys
import collections

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

Edge = collections.namedtuple('Edge', ['s', 't', 'cost'])
    
V, E = map(int, sys.stdin.readline().split())
edges = sorted([Edge(*map(int, line.split())) for line in sys.stdin], key=lambda e: e.cost)
uf = UnionFind(V)
min_cost = 0
for edge in edges:
    if not uf.are_same(edge.s, edge.t):
        uf.union(edge.s, edge.t)
        min_cost += edge.cost
print(min_cost)