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:
import sys
import collections
import heapq
import math

Edge = collections.namedtuple('Edge', ['s', 't', 'cost'])
    
V, E = map(int, sys.stdin.readline().split())
edges = collections.defaultdict(list)
for line in sys.stdin:
    e = Edge(*map(int, line.split()))
    edges[e.s].append(e)
    edges[e.t].append(Edge(e.t, e.s, e.cost))

heap = [(e.cost, e) for e in edges[0]]
heapq.heapify(heap)
nodes = {0}
min_cost = 0
while heap:
    _, edge = heapq.heappop(heap)
    if edge.t not in nodes:
        nodes.add(edge.t)
        for e in edges[edge.t]:
            heapq.heappush(heap, (e.cost, e))
        min_cost += edge.cost
print(min_cost)

Submission status: Accepted

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

def union(x, y):
    x = findSet(x)
    y = findSet(y)
    link(x, y)


def link(x, y):
    if r[x] > r[y]:
        p[y] = x

    else:
        p[x] = y
        if r[x] == r[y]: r[y] = r[y] + 1


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

    return p[x]


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



if __name__ == '__main__':
    p, r = [], []

    n_V, n_E = map(int, input().split())

    for i in range(n_V):
        p.append(i)
        r.append(0)

    Es = []
    for _ in range(n_E):
        s, t, w = map(int, input().split())
        Es.append(Edge(s, t, w))

    Es.sort(key=lambda e : e.w)

    sum_w = 0
    for e in Es:
        if not same(e.s, e.t):
            union(e.s, e.t)
            sum_w += e.w

    print(sum_w)

Submission status: Accepted

Solution code:
class Vertex:
    def __init__(self, p):
        self.p = p
        self.r = 0


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


def union(x, y):
    x = findSet(x)
    y = findSet(y)
    link(x, y)


def link(x, y):
    if V[x].r > V[y].r:
        V[y].p = x

    else:
        V[x].p = y
        if V[x].r == V[y].r: V[y].r = V[y].r + 1


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

    return V[x].p


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



if __name__ == '__main__':
    n_V, n_E = map(int, input().split())

    #
    V = []
    for i in range(n_V):
        V.append(Vertex(i))

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

    #
    E.sort(key=lambda e : e.w)

    #
    sum_w = 0
    for e in E:
        if not same(e.s, e.t):
            union(e.s, e.t)
            sum_w += e.w

    print(sum_w)

Submission status: Accepted

Solution code:
# Minimum Spanning Tree
p = []
rank = []
edge = []
cost = 0

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

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

def link(x, y):
    global p, rank
    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 same(x, y):
    if findSet(x) == findSet(y):
        return 1
    else:
        return 0   

[v, e] = list(map(int, input().split()))
for i in range(v):
    makeSet(i)

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

edge.sort()

while v > 1:
    min = edge.pop(0)
    if not same(min[1], min[2]):
        union(min[1], min[2])
        cost += min[0]
        v -= 1

print(cost)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.sizes = [0]*n

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            retrn;
        if self.sizes[x] < self.sizes[y]:
            x,y = y,x

        self.par[y] = x;
        self.sizes[x] += self.sizes[y]

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

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

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

def kruskal(edges, n):
    edges = sorted(edges)
    uf = UnionFind(n)
    min_cost = 0

    for edge in edges:
        if not uf.same(edge.s, edge.t):
            min_cost += edge.w
            uf.unite(edge.s, edge.t)

    return min_cost

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

Submission status: Accepted

Solution code:
"""
Kruskal
"""
from heapq import heappop, heappush

v_num, e_num = map(int, input().split())
pair_lst = [i for i in range(v_num)]
que = []
for _ in range(e_num):
  s, t, w = map(int, input().split())
  heappush(que, (w, s, t))

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

length_sum = 0
while que:
  w, s, t = heappop(que)
  root_s = find(s)
  root_t = find(t)
  if root_s != root_t:
    pair_lst[root_s] = root_t
    length_sum += w

print(length_sum)

Submission status: Accepted

Solution code:
class DisjointSet():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)

    def make_set(self, x):
        self.par[x] = x
        self.rank[x] = 0

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

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

class Edge():
    def __init__(self, source=0, target=0, cost=0):
        self.source = source
        self.target = target
        self.cost = cost

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

def kruskal(N, edges):
    # 今回は総コストのみ
    total_cost = 0
    edges = sorted(edges)

    dset = DisjointSet(N)

    source, target = 0, 0
    for i in range(E):
        e = edges[i]
        if not dset.same_check(e.source, e.target):
            total_cost += e.cost
            dset.unite(e.source, e.target)
    return total_cost

V, E = list(map(int, input().split(' ')))
edges = []
for i in range(E):
    s, t, d = list(map(int, input().split(' ')))
    edges.append(Edge(s, t, d))
print(kruskal(V, edges))

Submission status: Accepted

Solution code:

# input V, E
v, e = map(int, input().split())


# input weighted edges into priority queue
import heapq
h = []
for i in range(e):
	s, t, w = map(int, input().split())
	heapq.heappush(h, (w, s, t))


# initialize union find tree for vertices
p = [i for i in range(v)]
rank = [0 for i in range(v)]

def union(x, y):
 link(findSet(x), findSet(y))

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

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


def unite(x, y):
 union(x, y)

def same(x, y):
 x = findSet(x)
 y = findSet(y)
 if x == y:
  return True
 else :
  return False


# search MST
s = 0
for i in range(e):
	edge = heapq.heappop(h)
	if same(edge[1], edge[2]) == False:
		s = s + edge[0]
		unite(edge[1], edge[2])

# print sum of weights
print(s)

Submission status: Accepted

Solution code:
import heapq

def find_root(x):
  if x == nodes[x]:
    return x
  else:
    root = nodes[x] = find_root(nodes[x])
    return root

nv, ne = map(int, input().split())
nodes = [i for i in range(nv)]
q = []

for _ in range(ne):
  s, t, w = map(int, input().split())
  heapq.heappush(q, (w, s, t))

sum = 0

while q:
  w, s, t = heapq.heappop(q)
  root_s = find_root(s)
  root_t = find_root(t)
  if root_s != root_t:
    nodes[root_s] = root_t
    sum += w

print(sum)

Submission status: Accepted

Solution code:
v,e = map(int, input().split())
adj = [list(map(int, input().split())) for i in range(e)]
adj.sort(key = lambda x:x[2])
group = [[i] for i in range(v)]
key = [i for i in range(v)]
sum = 0
for i,j,k in adj:
    if key[i] != key[j]:
        h = key[j]
        group[key[i]] += group[h]
        sum += k
        for t in group[h]:
            key[t] = key[i]
        group[h] = []
        if len(group[key[i]]) == v:
            break
print(sum)

Submission status: Accepted

Solution code:
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def same(x, y):
    return root(x) == root(y)

def unite(x, y):
    x = root(x)
    y = root(y)
    par[x] = y

v,e = map(int, input().split())
adj = [list(map(int, input().split())) for i in range(e)]
adj.sort(key = lambda x:x[2])
par = [i for i in range(v)]
sum = 0

for i,j,k in adj:
    if not same(i, j):
        sum += k
        unite(i, j)
print(sum)

Submission status: Accepted

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

from collections import defaultdict

MAX = 10000
infty = -1

class Disjoint():
    def __init__():
        return

def getRoot(x):
    global v
    for _ in range(v+1):
        if dic[x]["parent"] == x:
            return x
        x = dic[x]["parent"]

def unite(x, y):
    r = getRoot(x)
    l = getRoot(y)
    a = dic[r]["rank"]
    b = dic[l]["rank"]

    if a == b:
        dic[r]["rank"] += 1
        dic[l]["parent"] = r

    elif a > b:
        dic[l]["rank"] = 0
        dic[l]["parent"] = r

    elif a < b:
        dic[r]["rank"] = 0
        dic[r]["parent"] = l

lines = stdin.readlines()
dic = defaultdict()
v, e = map(int, lines[0].split())
#E = [[lines[i+1].split()[0], lines[i+1].split()[1], lines[i+1].split()[2],] for i in range(e)]
E = [ list(map(int, lines[i+1].split())) for i in range(e)]
E = sorted(E, key=lambda x:x[2])

# Eの要素を整列
E = sorted(E, key=lambda x:x[2])
# V に対応した互に素な集合Sを生成する
for _ in range(v):
    dic[_] = {"rank":0,"parent":_}
# 辺の集合Kを空にする
k = 0
total = 0

for edge in E:
    if getRoot(edge[0]) != getRoot(edge[1]):
        unite(edge[0], edge[1])
        k += 1
        total += edge[2]

print(total)

Submission status: Accepted

Solution code:
import heapq
v,e=map(int,input().split())
adj=[[] for _ in range(v)]
for _ in range(e):
  a,b,c=map(int,input().split())
  adj[a].append((b,c))
  adj[b].append((a,c))

visit=[0]*v
pq=[]
for next,w in adj[0]:
  heapq.heappush(pq,(w,next))
visit[0]=1
ans=0
while pq:
  w,next=heapq.heappop(pq)
  if visit[next]:
    continue
  visit[next]=1
  ans+=w
  for next,w in adj[next]:
    if not visit[next]:
      heapq.heappush(pq,(w,next))
print(ans)

Submission status: Accepted

Solution code:
# e1 will be less than e2
def ifcycle(e1,e2):
    while uf[e1]>=0:
        e1=uf[e1]
    while uf[e2]>=0:
        e2=uf[e2]
    if e1==e2:
        return True
    if uf[e1]<=uf[e2]:
        uf[e1]+=uf[e2]
        uf[e2]=e1
    else:
        uf[e2]+=uf[e1]
        uf[e1]=e2
        return False
    
    
x,y=map(int,input().split())
a=[]
# for union-find
uf=[-1]*x
for i in range(y):
    v1,v2,v3=map(int,input().split())
    a.append([v3,v1,v2])
a.sort() 
ans=0 ; cnt=0
for p in range(y):
    w,s,t=a[p]
    if not ifcycle(s,t):
        ans+=w
        cnt+=1
        if cnt>=x: print(w)

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parent = [i for i in range(self.n)]
    self.rank = [0] * self.n
  
  def find_root(self, x):
    if self.parent[x] == x:
      return x
    else:
      self.parent[x] = self.find_root(self.parent[x])
      return self.parent[x]
  
  def unite(self, x, y):
    rx = self.find_root(x)
    ry = self.find_root(y)
    if rx == ry:
      return
    if self.rank[rx] < self.rank[ry]:
      self.parent[rx] = ry
    else:
      self.parent[ry] = rx
      if self.rank[rx] == self.rank[ry]:
        self.rank[rx] += 1
  
  def is_same(self, x, y):
    return self.find_root(x) == self.find_root(y)

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

uf = UnionFind(V)
total = 0
for e in edges:
  w, s, t = e
  if uf.is_same(s, t):
    continue
  uf.unite(s, t)
  total+= w
print(total)

Submission status: Accepted

Solution code:
import _heapq
inf=float("inf")


def prim():
    color=["white" for _ in range(v)]
    D=[inf for _ in range(v)]
    M=[[] for _ in range(v)]

    for s,t,w in STW:
        M[s].append([w,t])
        M[t].append([w,s])

    queue=[[0,0]]
    _heapq.heapify(queue)
    color[0]="gray"
    D[0]=0

    while len(queue)>0:
        num=_heapq.heappop(queue)[1]
        if color[num]=="black":continue
        color[num]="black"

        for i,j in M[num]:
            if i<D[j] and color[j]!="black":
                color[j]="gray"
                D[j]=i
                _heapq.heappush(queue,[i,j])

    return D


v,e=map(int,input().split())
STW=[list(map(int,input().split())) for _ in range(e)]
print(sum(prim()))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


class UnionFind:
    """Union Find class.

    "Path compression" and "Union by rank" are used.

    References:
        <https://en.wikipedia.org/wiki/Disjoint-set_data_structure>
    """

    def __init__(self, N):
        self.N = N
        self.__make_set()

    def __make_set(self):
        self._parent = list(range(self.N))
        self._rank = [0] * self.N
        self._size = [1] * self.N

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

    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)

        if x_root == y_root:
            return

        x_rank = self._rank[x_root]
        y_rank = self._rank[y_root]
        if x_rank > y_rank:
            self._parent[y_root] = x_root
            self._size[x_root] += self._size[y_root]
        elif x_rank < y_rank:
            self._parent[x_root] = y_root
            self._size[y_root] += self._size[x_root]
        else:
            self._parent[y_root] = x_root
            self._rank[x_root] += 1
            self._size[x_root] += self._size[y_root]

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

    def size(self, x):
        return self._size[self.find(x)]


def main():
    V, E = map(int, input().split())
    stw = [None] * E
    for i in range(E):
        stw[i] = tuple(map(int, input().split()))

    stw.sort(key=lambda x: x[2])
    uf = UnionFind(V)

    ans = 0
    for s, t, w in stw:
        if uf.same_set(s, t):
            continue
        uf.union(s, t)
        ans += w

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, num):
        self.parent = [i for i in range(num + 1)]

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

    def union(self, node1, node2):
        node1 = self.find(node1)
        node2 = self.find(node2)
        if node1 == node2:
            return
        if self.parent[node1] > self.parent[node2]:
            node1, node2 = node2, node1
        self.parent[node2] = node1
        return

    def same(self, node1, node2):
        return self.find(node1) == self.find(node2)


# edges is array which consists of [cost, frm, to] elements
def kruskal(vertex_num, edges):
    ans = 0
    uf = UnionFind(vertex_num)
    # sort edges in cost ascending order
    edges.sort()
    for edge in edges:
        cost, frm, to = edge
        if uf.same(frm, to) is False:
            uf.union(frm, to)
            ans += cost
    return ans


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

print(kruskal(v, edges))

Submission status: Accepted

Solution code:
# 64 Kruskal


class UnionFind():
    def __init__(self, v):
        self.rank = [1] * v
        self.par = [x for x in range(v)]
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        if self.find(x) == self.find(y):
            return False
        else:
            p_x = self.find(x)
            p_y = self.find(y)
            if self.rank[p_x] >= self.rank[p_y]:
                self.par[p_y] = p_x
                self.rank[p_y] += 1
            else:
                self.par[p_x] = p_y
                self.rank[p_x] += 1
    
    def same(self, x, y):
        p_x = self.find(x)
        p_y = self.find(y)
        return p_x == p_y
    
v, e = map(int, input().split())
e_l = [[int(x) for x in input().split()] for y in range(e)]
e_l.sort(key= lambda x: x[2])

def Kruskal(s):
    ans = 0
    uf = UnionFind(v)

    for _s, _t, _w in e_l:
        if not uf.same(_s, _t):
            uf.unite(_s, _t)
            ans += _w
    return ans
            
print(Kruskal(0))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
v_num, e_num = map(int, input().split())
pair_lst = [i for i in range(v_num)]
que = []
for _ in range(e_num):
  s, t, w = map(int, input().split())
  heappush(que, (w, s, t))
def find(x):
  if x == pair_lst[x]:
    return x
  else:
    tmp = find(pair_lst[x])
    pair_lst[x] = tmp
    return tmp

length_sum = 0
while que:
  w, s, t = heappop(que)
  root_s = find(s)
  root_t = find(t)
  if root_s != root_t:
    pair_lst[root_s] = root_t
    length_sum += w

print(length_sum)

Submission status: Accepted

Solution code:
E = []
v, e = map(int, input().split())
for _ in range(e):
    s, t, w = map(int, input().split())
    E.append((w, s, t))


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

    def findset(self, A):
        if self.parent[A] < 0:
            return A
        self.parent[A] = self.findset(self.parent[A])
        return self.parent[A]

    def size(self, A):
        return -self.parent[self.findset(A)]

    def unite(self, A, B):
        A = self.findset(A)
        B = self.findset(B)

        if A == B:
            return False

        if self.size(A) > self.size(B):
            A, B = B, A

        self.parent[A] += self.parent[B]
        self.parent[B] = A

        return True

    def is_same(self, A, B):
        return self.findset(A) == self.findset(B)
        

def kruskal(N):
    edges = sorted(E)
    ans = 0
    union = UnionFind(N)
    cnt = 0
    for w, s, t in edges:
        if cnt == N-1:
            break

        if union.is_same(s, t):
            continue
        else:
            union.unite(s, t)
            ans += w
            cnt += 1
            
    return ans

print(kruskal(v))

Submission status: Accepted

Solution code:
# Kruskal's Algorithm

def kruskal():
    '''
    最小全域木のコストを求める
    '''
    cost = 0
    edge.sort()

    for c, u, v in edge:
        if same(u, v):
            continue
        union(u, v)
        cost += c

    return cost


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


def union(x, y):
    '''
    xとyの属する集合を併合する
    '''
    x = find(x)
    y = find(y)
    
    if x == y:
        return False

    if par[x] > par[y]:
        x, y = y, x

    par[x] += par[y]
    par[y] = x
    return True


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


################################
n, w = map(int, input().split())  # n:頂点数　w:辺の数

par = [-1] * n  # 根: -size, 葉: 親の頂点
edge = []       # edge[i]:iから出る辺の[重み,行先]の配列
for _ in range(w):
    x, y, z = map(int, input().split())
    edge.append([z, x, y])

print(kruskal())

Submission status: Accepted

Solution code:
class Graph:
    class Edge:
        def __init__(self, to, cost):
            """
            :param to:  終点ノード
            :param cost: 辺の重み
            """
            self.to, self.cost = to, cost

    def __init__(self, n, directed=False, decrement=True, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.edges = [[] for _ in range(self.n)]
        self.edges2 = []                            # ワーシャルフロイド用
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y, cost in edges:
            self.add_edge(x, y, cost)

    def add_edge(self, x, y, cost):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].append(self.Edge(y, cost))
        self.edges2.append((x, y, cost))
        if self.directed == False:
            self.edges[y].append(self.Edge(x, cost))
            self.edges2.append((y, x, cost))

    def prim(self):
        """
        :return: 最小全域木を選んだ時の重さの総和
        """
        start = 0  # 解析のスタート地点を決める。どこでもいい
        visit = [False] * self.n  # 各頂点までの最短距離
        next_set = [(0, start)]
        res = 0
        while next_set:
            dist, p = heappop(next_set)  # 近いところから順に確定させていく必要があるため、heappop を用いる
            if visit[p]:
                continue
            visit[p] = True
            res += dist  # クラスカル法と違って隣接点を調べていくので、足される数の大きさはバラバラ
            for edge in self.edges[p]:
                q, cost = edge.to, edge.cost
                if visit[q]:
                    continue
                heappush(next_set, (cost, q))  # q を介して他の頂点に行く可能性を考える。q に行くまでの最短距離が明らかになっている点が重要
        return res

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        if self.directed:
            G = nx.DiGraph()
        else:
            G = nx.Graph()
        for x in range(self.n):
            for edge in self.edges[x]:
                G.add_edge(x + self.decrement, edge.to + self.decrement, weight=edge.cost)


        edge_labels = {(i, j): w['weight'] for i, j, w in G.edges(data=True)}
        pos = nx.spring_layout(G)
        nx.draw_networkx(G, pos, with_labels=True)
        nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
        plt.axis("off")
        plt.show()

##############################################################################################################
import sys
input = sys.stdin.readline
from heapq import *


N, M = map(int, input().split())
graph = Graph(N, directed=False, decrement=True)
for _ in range(M):
    x, y, cost = map(int, input().split())
    graph.add_edge(x, y, cost)

print(graph.prim())

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, n):
    self.parent = [i for i in range(n)]
    self.height = [0 for i in range(n)]
    
  def get_root(self, i):
    if self.parent[i] == i:
      return i
    else:
      self.parent[i] = self.get_root(self.parent[i])
      return self.parent[i]
    
  def unite(self, i, j):
    root_i = self.get_root(i)
    root_j = self.get_root(j)
    if root_i != root_j:
      if self.height[root_i] < self.height[root_j]:
        self.parent[root_i] = root_j
      else:
        self.parent[root_j] = root_i
        if self.height[root_i] == self.height[root_j]:
          self.height[root_i] += 1
          
  def is_in_group(self, i, j):
    if self.get_root(i) == self.get_root(j):
      return True
    else:
      return False
    
def kruskal(V, e_list):
  #V := ノードの数
  #e_list := [[始点ノード, 終点ノード, コスト], ...]
  e_cost_sorted = []
  for e in e_list:
    e_cost_sorted.append([e[2], e[0], e[1]])
  e_cost_sorted.sort()
  uf_tree = UnionFind(V)
  cost = 0
  for k in range(len(e_cost_sorted)):
    c = e_cost_sorted[k][0]
    i = e_cost_sorted[k][1]
    j = e_cost_sorted[k][2]
    if not uf_tree.is_in_group(i, j):
      uf_tree.unite(i, j)
      cost += c
  print(cost)
  
V, E = map(int, input().split())
e_list = []
for i in range(E):
  e_list.append(list(map(int, input().split())))
kruskal(V, e_list)

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self,size):
        self.rank = [None]*size
        self.p = [None]*size
        for i in range(size):
            self.make_set(i)
        return
    
    def make_set(self,x):
        self.p[x] = x
        self.rank[x] = 0
        return
    
    def same(self,x,y):
        return self.find_set(x) == self.find_set(y)
        
    def unite(self,x,y):
        self.link(self.find_set(x),self.find_set(y))
        return
    
    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 find_set(self,x):
        if x != self.p[x]:
            self.p[x] = self.find_set(self.p[x])
        return self.p[x]
    
class Edge:
    def __init__(self,source,target,cost):
        self.source = source
        self.target = target
        self.cost = cost
        
def kruskal(edges):
    edges.sort(key=lambda x: x.cost)
    
    S = DisjointSet(n)
    K = []
    
    for i in range(m):
        if S.find_set(edges[i].source) != S.find_set(edges[i].target):
            K.append(edges[i])
            S.unite(edges[i].source,edges[i].target)
    return K

n,m = map(int,input().split())
edges = []

for i in range(m):
    s,t,w = map(int,input().split())
    edges.append(Edge(s,t,w))
    
K = kruskal(edges)

cost = 0
while K:
    edge = K.pop()
    cost += edge.cost
print(cost)

Submission status: Accepted

Solution code:
import heapq
def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

#########################
n,w = map(int,input().split())

edge = [[] for i in range(n)]
#隣接リスト edge[i]:[コスト,行先]
for i in range(w):
    x,y,z = map(int,input().split())
    edge[x].append([z,y])
    edge[y].append([z,x])
print(prim_heap())

Submission status: Accepted

Solution code:
class UnionFindTree():

    def __init__(self, n):
        #木全体の要素数
        self.n  = n
        #root[x]<0ならそのノードが根でありその値が木の要素数
        self.root = [-1] * (n+1)
        #ランク
        self.rank = [1] * (n+1)

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

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

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

    def count_node(self,x):
        return -1 * self.root[self.find_root(x)]
v, e = map(int, input().split())
edges = []
for _ in range(e):
    s, t, w = map(int, input().split())
    edges.append((w, s, t))

#edgesは予めsortする
edges.sort()

def kuruskal(n, edges):
    uft = UnionFindTree(n)
    res = 0
    for e in edges:
        w, s, t = e
        if not uft.is_same(s, t):
            res += w
            uft.unite(s, t)
    return res

print(kuruskal(v, edges))

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
G = []
for _ in [0]*M:
    a, b, c = map(int, input().split())
    heappush(G, (c, a, b))


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

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if x > y:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        self.u -= 1
        return True

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

    def size(self, x):
        return -self.d[self.root(x)]

    def num_union(self):
        return self.u


u = UnionFind(N)
ans = 0
while u.num_union() > 1:
    c, a, b = heappop(G)
    if u.same(a, b):
        continue
    u.unite(a, b)
    ans += c
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

nv,ne=map(int,input().split())
pair_lst = [i for i in range(nv)]
que=[]
for i in range(ne):
    si,ti,wi=map(int,input().split())
    heappush(que,(wi,si,ti))

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

length_sum = 0
while que:
    w, s, t = heappop(que)
    root_s = find(s)
    root_t = find(t)
    if root_s != root_t:
        pair_lst[root_s] = root_t
        length_sum += w

print(length_sum)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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


def main():
    V, E = map(int, readline().split())
    L = []
    for _ in range(E):
        s, t, w = map(int, readline().split())
        L.append([s, t, w])
    # 重みが軽い順にソート
    L.sort(key=lambda x: x[2])
    uf = UnionFind(V)
    ans = 0
    for i in range(E):
        s, t, w = L[i]
        if not uf.same(s, t):
            uf.union(s, t)
            ans += w
    print(ans)


if __name__ == '__main__':
    main()