Problem:


Score : 500 points

Problem Statement

There are N towns on a plane. The i-th town is located at the coordinates (x_i,y_i). There may be more than one town at the same coordinates.

You can build a road between two towns at coordinates (a,b) and (c,d) for a cost of min(|a-c|,|b-d|) yen (the currency of Japan). It is not possible to build other types of roads.

Your objective is to build roads so that it will be possible to travel between every pair of towns by traversing roads. At least how much money is necessary to achieve this?

Constraints

2 ≤ N ≤ 10^5

0 ≤ x_i,y_i ≤ 10^9

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print the minimum necessary amount of money in order to build roads so that it will be possible to travel between every pair of towns by traversing roads.

Sample Input 1

3
1 5
3 9
7 8

Sample Output 1

3

Build a road between Towns 1 and 2, and another between Towns 2 and 3. The total cost is 2+1=3 yen.

Sample Input 2

6
8 3
4 9
12 19
18 1
13 5
7 6

Sample Output 2

8



Sample input:
3
1 5
3 9
7 8


Sample output:
3

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import heapq
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 size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def solve(N: int, x: "List[int]", y: "List[int]"):
    xy = []
    edges = [] # cost,node1,node2
    for i in range(N):
        xy.append((i,x[i],y[i]))

    x_xy = sorted(xy, key= lambda x:x[1])
    y_xy = sorted(xy, key= lambda x:x[2])
    
    for i in range(N-1):
        cur = x_xy[i]
        next = x_xy[i+1]
        edges.append((next[1]-cur[1],next[0],cur[0]))
        cur = y_xy[i]
        next = y_xy[i+1]
        edges.append((next[2]-cur[2],next[0],cur[0]))

    edges.sort(key= lambda x: x[0])
    uf = UnionFind(N)
    answer = 0
    
    for cost,node1,node2 in edges:
        if uf.same(node1,node2):
            continue

        answer += cost
        uf.union(node1,node2)
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
from scipy.sparse import csr_matrix
import numpy as np

N = int(input())

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]
#print(XY)

edge = set()

#sortする際にインデックス1,2でそれぞれsortする
for key in [itemgetter(1),itemgetter(2)]:
  XY.sort(key = key)
  #print("XY",XY)
  for i in range(N-1):
    i1,x1,y1 = XY[i]
    i2,x2,y2 = XY[i+1]
    d = min(abs(x1-x2),abs(y1-y2))
    edge.add((i1,i2,d))
    
#print(edge)    
    
# csr形式に直す
row,col,value = zip(*edge)
#print(row,col,value)

value = np.array(value,dtype=int)
graph = csr_matrix((value,(row,col)),shape=(N,N))
#print(graph)

# 最小全域木
from scipy.sparse.csgraph import minimum_spanning_tree
tree = minimum_spanning_tree(graph, overwrite = True).astype(int)
#print(tree)

answer = tree.sum()
print(answer)

Submission status: Accepted

Solution code:
import sys
import heapq
n = int(input())
v_ls = []
x_ls = []
y_ls = []
for j in range(n):
    x, y = [int(i) for i in sys.stdin.readline().split()]
    v_ls.append((j, x, y))

graph = {i:[] for i in range(n)}
v_ls.sort(key=lambda x:x[1])
for i, v in enumerate(v_ls[:-1]):
    _from = v
    _to = v_ls[i + 1]
    diff = _to[1] - _from[1]
    graph[_from[0]].append((_to[0], diff))
    graph[_to[0]].append((_from[0], diff))

v_ls.sort(key=lambda x:x[2])
for i, v in enumerate(v_ls[:-1]):
    _from = v
    _to = v_ls[i + 1]
    diff = _to[2] - _from[2]
    graph[_from[0]].append((_to[0], diff))
    graph[_to[0]].append((_from[0], diff))

v_ls.sort(key=lambda x:x[0])
already = set()
cur = [(0, 0)]
cost = 0
while len(cur) > 0:
    cur_cost, cur_ind = heapq.heappop(cur)
    if cur_ind in already:
        continue
    already.add(cur_ind)
    cost += cur_cost
    for _next, next_cost in graph[cur_ind]:
        if _next in already:
            continue
        heapq.heappush(cur, (next_cost, _next))
    if len(already) == n:
        break
print(cost)

Submission status: Accepted

Solution code:
from operator import itemgetter as get

class UnionFind():
	def __init__(self, n):
		self.n = n
		self.root = [-1] * (n + 1)
		self.rank = [0] * (n + 1)

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

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

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


def main():
	n, *L = map(int, open(0).read().split())
	x_order = sorted([(x, y, i) for i, (x, y) in enumerate(zip(*[iter(L)] * 2))])
	con = []
	for p1, p2 in zip(x_order, x_order[1:]):
		con.append((p1[2], p2[2], min(abs(p1[0] - p2[0]), abs(p1[1] - p2[1]))))
	y_order = sorted(x_order, key=get(1))
	for p1, p2 in zip(y_order, y_order[1:]):
		con.append((p1[2], p2[2], min(abs(p1[0] - p2[0]), abs(p1[1] - p2[1]))))
	uf = UnionFind(n)
	ans = 0
	for i, j, c in sorted(con, key=get(2)):
		if uf.isSame(i, j):
			continue
		ans += c
		uf.unite(i, j)
	print(ans)


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import heapq as hq

N = int(input())
c = []
for i in range(N):
  x, y = map(int, input().split())
  c.append((i, x, y))

cx = sorted(c, key=lambda x: x[1])
cy = sorted(c, key=lambda x: x[2])

edge = [set() for i in range(N)] # edge[from][to] = weight

for i in range(1, N):
  edge[cx[i-1][0]].add((cx[i][1]-cx[i-1][1], cx[i][0]))
  edge[cx[i][0]].add((cx[i][1]-cx[i-1][1], cx[i-1][0]))

  edge[cy[i-1][0]].add((cy[i][2]-cy[i-1][2], cy[i][0]))
  edge[cy[i][0]].add((cy[i][2]-cy[i-1][2], cy[i-1][0]))
  
for i in range(N-1):
  edge[cx[i][0]].add((cx[i+1][1]-cx[i][1], cx[i+1][0]))
  edge[cx[i+1][0]].add((cx[i+1][1]-cx[i][1], cx[i][0]))

  edge[cy[i][0]].add((cy[i+1][2]-cy[i][2], cy[i+1][0]))
  edge[cy[i+1][0]].add((cy[i+1][2]-cy[i][2], cy[i][0]))
  

q = [(0, 0)]
used = [False] * N
un = 0
r = 0

while q and un < N:
  w, prev = hq.heappop(q)

  if used[prev]: continue
  
  used[prev] = True
  un += 1
  r += w
  
  for w, to in edge[prev]:
    if not used[to]:
      hq.heappush(q, (w, to))
print(r)

Submission status: Accepted

Solution code:
import heapq
class UnionFind:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N # 最初はそれぞれのノードが誰ともUnionをつくってないから木の深さが０
        self.count = 0 # unite回数
    
    # 根を返す
    def root(self, a):
        if self.parent[a] == a:
            return a
        else:
            # 親を見に行く
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    
    # 同じUnionに属するかどうか
    def is_same(self, a, b):
        return self.root(a) == self.root(b)
    
    # 同じUnionにする
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return 
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]:
                self.rank[ra] += 1
        self.count += 1

N = int(input())

cities = [tuple(map(int, input().split())) for _ in range(N)]

"""
AtCoder Beginner Contest 065 D
あるノードについてx座標の差とや座標の差それぞれの絶対値の小さいほうがコストになる
最小全域木を作ることでコストを最小にする
なので、
・x座標が小さい順で並べ替えたノードリスト
・ｙ座標が小さい順で並べ替えたノードリスト
を作って、それらのノード間に辺が張られているとする。
これで最小全域木ができるまでクラスカル法とかで頑張る
"""
xs = []
ys = []
for i,(x,y) in enumerate(cities):
    xs.append((x, i))
    ys.append((y, i))

xs.sort()
ys.sort()

es = []
for (xa, a), (xb,b) in zip(xs, xs[1:]):
    es.append((abs(xa-xb), a, b))

for (ya, a), (yb, b) in zip(ys, ys[1:]):
    es.append((abs(ya-yb), a, b))

es.sort()

uf = UnionFind(N)

totalcost = 0
"""
esは辺のコストが小さい順で並んでいるので、コストが小さい順に繋がれる
また、esは2N個なので、十分間に合う
"""
for c, a, b in es:
    if uf.is_same(a,b):
        continue
    uf.unite(a,b)
    totalcost += c

print(totalcost)

Submission status: Accepted

Solution code:
import heapq
import sys
input = sys.stdin.readline
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= int(input())

edge = [[] for i in range(n)]
#隣接リスト edge[i]:[コスト,行先]
l=[]
for i in range(n):
    a,b=map(int,input().split())
    l.append([a,b,i])
l=sorted(l,key=lambda x: -x[0])
for i in range(n-1):
    x=l[i][2]
    y=l[i+1][2]
    z=l[i][0]-l[i+1][0]
    edge[x].append([z,y])
    edge[y].append([z,x])
l=sorted(l,key=lambda x: -x[1])
for i in range(n-1):
    x=l[i][2]
    y=l[i+1][2]
    z=l[i][1]-l[i+1][1]
    edge[x].append([z,y])
    edge[y].append([z,x])
print(prim_heap())

Submission status: Accepted

Solution code:
# 解説

def solve() -> None:
    from collections import namedtuple
    from heapq import heappush, heappop
    from operator import attrgetter
    pt = namedtuple('pt', 'x y idx')

    n = int(input())
    cities = []
    for idx in range(n):
        x, y = map(int, input().split())
        cities.append(pt(x=x, y=y, idx=idx))

    g = tuple(set() for _ in range(n))

    xs = sorted(cities, key=attrgetter('x'))
    for a, b in zip(xs, xs[1:]):
        g[a.idx].add((b.x - a.x, b.idx))
        g[b.idx].add((b.x - a.x, a.idx))

    ys = sorted(cities, key=attrgetter('y'))
    for a, b in zip(ys, ys[1:]):
        g[a.idx].add((b.y - a.y, b.idx))
        g[b.idx].add((b.y - a.y, a.idx))

    ret = 0
    h = [(0, 0)]
    used = [False] * n
    count = 0

    while True:
        c, v = heappop(h)
        if used[v]:
            continue
        used[v] = True
        count += 1
        ret += c
        if count == n:
            break
        for c_, u in g[v]:
            if used[u]:
                continue
            heappush(h, (c_, u))

    return ret


if __name__ == '__main__':
    print(solve())

# 最小全域木

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
pointx=[]
pointy=[]
for i in range(n):
    x,y=map(int,input().split())
    pointx.append((x,i))
    pointy.append((y,i))
pointx.sort()
pointy.sort()
G=[[] for i in range(n)]
for i in range(n-1):
    dx=abs(pointx[i+1][0]-pointx[i][0])
    G[pointx[i][1]].append((dx,pointx[i+1][1]))
    G[pointx[i+1][1]].append((dx,pointx[i][1]))
    dy=abs(pointy[i+1][0]-pointy[i][0])
    G[pointy[i][1]].append((dy,pointy[i+1][1]))
    G[pointy[i+1][1]].append((dy,pointy[i][1]))
import heapq
q=[]
check=[False]*n
check[0]=True
for i in G[0]:
    heapq.heappush(q,i)
ans=0
while len(q)>0:
    now=heapq.heappop(q)
    if not check[now[1]]:
        ans+=now[0]
        check[now[1]]=True
        for i in G[now[1]]:
            heapq.heappush(q,i)
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop

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

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n))
        self.ranks = [0 for _ in range(n)]
 
    def get_root(self, x):
        if self.parents[x] == x:
            return x
        self.parents[x] = self.get_root(self.parents[x])
        return self.parents[x]
 
    def merge(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)
        if x != y:
            if self.ranks[x] < self.ranks[y]:
                self.parents[x] = y
            else:
                self.parents[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1
 
def kruskal(n_nodes, edges):
    edges.sort(key=itemgetter(2))
    res = []
    uf = UnionFind(n_nodes)
    for e in edges:
        if uf.get_root(e[0]) != uf.get_root(e[1]):
            res.append(e)
            uf.merge(e[0], e[1])
    return res

N = INT()
xy = [LIST() for _ in range(N)]
ixy = list(enumerate(xy))
ixy.sort(key=lambda x:x[1][0])

edges = []

for (i, (x, y)), (j, (x1, y1)) in zip(ixy, ixy[1:]):
	edges.append((i, j, min(abs(x-x1), abs(y-y1))))

ixy.sort(key=lambda x:x[1][1])
for (i, (x, y)), (j, (x1, y1)) in zip(ixy, ixy[1:]):
	edges.append((i, j, min(abs(x-x1), abs(y-y1))))

tree = kruskal(N, edges)
print(sum(x[2] for x in tree))

Submission status: Accepted

Solution code:
# ABC065d
import sys
from operator import itemgetter
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def dist(x1, y1, x2, y2):
    return min(abs(x1-x2), abs(y1-y2))


n = int(input())
Aedges = []
Aedges2 = []
for i in range(n):
    x, y = map(int, input().split())
    Aedges.append((x, y, i))
    Aedges2.append((x, y, i))
Aedges.sort()
Aedges2.sort(key=itemgetter(1))
# print(Aedges)
# print(Aedges2)

edges = []

for i in range(1, n):
    edges.append((Aedges[i][0]-Aedges[i-1][0], Aedges[i][2], Aedges[i-1][2]))
for i in range(1, n):
    edges.append((Aedges2[i][1]-Aedges2[i-1][1],
                  Aedges2[i][2], Aedges2[i-1][2]))

edges.sort()


class UnionFind:
    def __init__(self, n):
        self.tree = [i for i in range(n)]

    def root(self, x):
        if(self.tree[x] == x):
            return x
        self.tree[x] = self.root(self.tree[x])
        return self.tree[x]  # 経路圧縮

    def same(self, x, y):  # xとyが同じ木に属するか
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if(x == y):
            return
        self.tree[x] = y


def kruskal(n, edges):  # edges: wでソート済み
    U = UnionFind(n)
    res = 0
    for e in edges:
        w, s, t = e
        if not U.same(s, t):
            res += w
            U.unite(s, t)
    return res


print(kruskal(n, edges))

Submission status: Accepted

Solution code:
def main():
    import heapq
    from sys import stdin
    input=stdin.readline
    class unionfind():
        #size:要素数,tree：unionfind木
        def __init__(self,size):#self,要素数
            self.size=size
            self.tree=[[i,1] for i in range(self.size)]#root,depth
        
        #rootを探す
        def root(self,index):
            if self.tree[index][0]==index:
                return index
            else:
                self.tree[index][0]=self.root(self.tree[index][0])
                return self.tree[index][0]
    
        #結合
        def unite(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1!=r2:
                d1,d2=self.tree[r1][1],self.tree[r2][1]
                if d1<=d2:
                    self.tree[r1][0]=r2
                    self.tree[r2][1]=max(d1+1,d2)
                else:
                    self.tree[r2][0]=r1
                    self.tree[r1][1]=max(d2+1,d1)
    
        #同じか判定
        def same(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            return r1==r2
    
    n=int(input())
    xy=[list(map(int,input().split())) for _ in [0]*n]
    xyz=[xy[i]+[i] for i in range(n)]
    x_sort=sorted(xyz,key=lambda x:x[0])
    y_sort=sorted(xyz,key=lambda x:x[1])
    g=[]
    heapq.heapify(g)
    for i in range(n-1):
        heapq.heappush(g,[abs(x_sort[i+1][0]-x_sort[i][0]),x_sort[i][2],x_sort[i+1][2]])
    for i in range(n-1):
        heapq.heappush(g,[abs(y_sort[i+1][1]-y_sort[i][1]),y_sort[i][2],y_sort[i+1][2]])
    u=unionfind(n)
    cnt=0
    while g:
        d,i,j=heapq.heappop(g)
        if u.same(i,j)==False:
            cnt+=d
            u.unite(i,j)
    print(cnt)
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

class UnionFind(object):
    def __init__(self,n):
        self.__par=list(range(n))
        self.__rank=[0]*n
        self.__size=[1]*n

    def root(self,k):
        if(self.__par[k]==k): return k
        self.__par[k]=self.root(self.__par[k])
        return self.__par[k]

    def unite(self,i,j):
        i=self.root(i); j=self.root(j)
        par=self.__par; rank=self.__rank; size=self.__size
        if(i==j): return False
        if(rank[i]>rank[j]):
            par[j]=i
            size[i]+=size[j]
        else:
            par[i]=j
            size[j]+=size[i]
            if(rank[i]==rank[j]): rank[j]+=1
        return True

    def size(self,k):
        return self.__size[self.root(k)]

def resolve():
    n=int(input())
    XYI=[0]*n
    for i in range(n):
        x,y=map(int,input().split())
        XYI[i]=(x,y,i)

    # Kruskal に使う可能性のある辺だけをグラフに追加する
    E=[]
    XYI.sort()
    for i in range(n-1):
        x0,y0,u=XYI[i]
        x1,y1,v=XYI[i+1]
        E.append((u,v,x1-x0))
    XYI.sort(lambda x:x[1])
    for i in range(n-1):
        x0,y0,u=XYI[i]
        x1,y1,v=XYI[i+1]
        E.append((u,v,y1-y0))

    # Kruskal method
    E.sort(lambda x:x[2])
    uf=UnionFind(n)
    ans=0
    for u,v,w in E:
        if(uf.unite(u,v)):
            ans+=w
    print(ans)
resolve()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])

def graphm():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(m):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((w,b))
        g[b].append((w,a))
    return n,m,g

def prim(n,g):
    edgelist = []
    used = [False for _ in range(n)]
    for edge in g[0]:
        heappush( edgelist, edge)
    used[0] = True
    res = 0 

    while len(edgelist)>0:
        minedge = heappop(edgelist)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = True
        for edge in g[v]:
            if not used[edge[1]]:
                heappush( edgelist, edge)
        res += minedge[0]
    return res

def main():
    n=inp()
    xy=[]
    for index in range(n):
        x,y = inpm()
        xy.append((x,y,index))
        
    g=[[] for _ in range(n)]
    xy.sort()
    for i in range(n-1):
        j = i+1
        w = min(abs(xy[i][0]-xy[j][0]),abs(xy[i][1]-xy[j][1]))
        a = xy[i][2]
        b = xy[j][2]
        g[a].append((w,b))
        g[b].append((w,a))
    xy.sort(key=lambda y:y[1])
    for i in range(n-1):
        j = i+1
        w = min(abs(xy[i][0]-xy[j][0]),abs(xy[i][1]-xy[j][1]))
        a = xy[i][2]
        b = xy[j][2]
        g[a].append((w,b))
        g[b].append((w,a))
    print( prim(n,g) )

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * 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, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])

def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    while True:
        d, v, u = heapq.heappop(edge)
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            n -= 1
            ans += d
        if n < 2: return ans
    return ans

n = int(input())
x, y = [None]*n, [None]*n

for i in range(n):
    a, b = map(int, input().split())
    x[i] = (a, i)
    y[i] = (b, i)

x.sort(key=lambda x:x[0])
y.sort(key=lambda y:y[0])

edge = []
for i in range(n-1):
    heapq.heappush(edge, (x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    heapq.heappush(edge, (y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

del x, y
print(kruskal(n, edge))

Submission status: Accepted

Solution code:
from operator import itemgetter
import heapq
 
N = int(input())
pos = [[int(p) for p in input().split()] for _ in range(N)]
 
pos.sort()
for i in range(N):
    pos[i].append(i)
    
Y = sorted(pos, key=itemgetter(1))
Y_idx = [0]*N
for i in range(N):
    Y_idx[Y[i][2]] = i
    
ans = 0
used = [0]*N
used[0] = 1
h = []
c = 1
idx = Y_idx[0]
heapq.heappush(h, (pos[c][0]-pos[c-1][0], 1))
if idx > 0:
    heapq.heappush(h, (Y[idx][1]-Y[idx-1][1], Y[idx-1][2]))
if idx < N-1:
    heapq.heappush(h, (Y[idx+1][1]-Y[idx][1], Y[idx+1][2]))
    
cnt = 0
while cnt < N-1:
    t = heapq.heappop(h)
    if used[t[1]] == 1:
        continue
    c = t[1]
    used[c] = 1
    cnt += 1
    ans += t[0]
    if c > 0 and used[c-1] == 0:
        heapq.heappush(h, (pos[c][0]-pos[c-1][0], c-1))
    if c < N-1 and used[c+1] == 0:
        heapq.heappush(h, (pos[c+1][0]-pos[c][0], c+1))
    idx = Y_idx[c]
    if idx > 0 and used[Y[idx-1][2]] == 0:
        heapq.heappush(h, (Y[idx][1]-Y[idx-1][1], Y[idx-1][2]))
    if idx < N-1 and used[Y[idx+1][2]] == 0:
        heapq.heappush(h, (Y[idx+1][1]-Y[idx][1], Y[idx+1][2]))
            
print(ans)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

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

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

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

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

class Kruskal:
    def __init__(self, Q, n):
        self.uf = UnionFind(n)
        self.cost = 0
        self.Q = Q
        for i in range(2 * (n - 1)):
            w, u, v = self.Q[i][0], self.Q[i][1], self.Q[i][2] 
            if self.uf.same_check(u, v) != True:
                self.uf.union(u, v)
                self.cost += w

#処理内容
def main():
    N = int(input())
    Lx = []
    Ly = []
    for i in range(N):
        x, y = getlist()
        Lx.append((x, i))
        Ly.append((y, i))
    Lx = sorted(Lx)
    Ly = sorted(Ly)
    Q = []

    for i in range(N - 1):
        u = Lx[i][1]
        v = Lx[i + 1][1]
        w = Lx[i + 1][0] - Lx[i][0]
        Q.append((w, u, v))
        u = Ly[i][1]
        v = Ly[i + 1][1]
        w = Ly[i + 1][0] - Ly[i][0]
        Q.append((w, u, v))
    Q = sorted(Q)
    Km = Kruskal(Q, N)
    print(Km.cost)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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 size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
town = [list(map(int,input().split()))+[i] for i in range(N)]

townx = sorted(town)
towny = sorted(town,key = lambda t : t[1])

road = []

for i in range(N-1):
    road.append([abs(townx[i][0]-townx[i+1][0]),townx[i][2],townx[i+1][2]])
    road.append([abs(towny[i][1]-towny[i+1][1]),towny[i][2],towny[i+1][2]])

road.sort()

uf = UnionFind(N)
ans = 0

for r in road:
    cost,t1,t2 = r
    if uf.same(t1,t2):
        continue
    uf.union(t1,t2)
    ans += cost
    
print(ans)

Submission status: Accepted

Solution code:
import operator
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n))
        self.ranks = [0 for _ in range(n)]

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

    def merge(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)
        if x != y:
            if self.ranks[x] < self.ranks[y]:
                self.parents[x] = y
            else:
                self.parents[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1


def kruskal(n_nodes, edges):
    edges.sort(key=operator.itemgetter(2))
    res = []
    uf = UnionFind(n_nodes)
    for e in edges:
        if uf.get_root(e[0]) != uf.get_root(e[1]):
            res.append(e)
            uf.merge(e[0], e[1])
    return res


n = ri()
ls = rils(n)
ls = list(enumerate(ls))

edges = []
ls.sort(key=lambda x: x[1][0])
for (i, (x0, y0)), (j, (x1, y1)) in zip(ls, ls[1:]):
    edges.append((i, j, min(abs(x0 - x1), abs(y0 - y1))))

ls.sort(key=lambda x: x[1][1])
for (i, (x0, y0)), (j, (x1, y1)) in zip(ls, ls[1:]):
    edges.append((i, j, min(abs(x0 - x1), abs(y0 - y1))))

res = kruskal(n, edges)
print(sum(x[2] for x in res))

Submission status: Accepted

Solution code:
import operator
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n + 1))
        self.ranks = [0 for _ in range(n + 1)]

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

    def merge(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)
        if x != y:
            if self.ranks[x] < self.ranks[y]:
                self.parents[x] = y
            else:
                self.parents[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1


def kruskal(n_nodes, edges):
    edges.sort(key=operator.itemgetter(2))
    res = []
    uf = UnionFind(n_nodes)
    for e in edges:
        if uf.get_root(e[0]) != uf.get_root(e[1]):
            res.append(e)
            uf.merge(e[0], e[1])
    return res


n = ri()
ls = rils(n)
ls = list(enumerate(ls))

edges = []
ls.sort(key=lambda x: x[1][0])
for (i, (x0, y0)), (j, (x1, y1)) in zip(ls, ls[1:]):
    edges.append((i, j, min(abs(x0 - x1), abs(y0 - y1))))

ls.sort(key=lambda x: x[1][1])
for (i, (x0, y0)), (j, (x1, y1)) in zip(ls, ls[1:]):
    edges.append((i, j, min(abs(x0 - x1), abs(y0 - y1))))

res = kruskal(n, edges)
print(sum(x[2] for x in res))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)


par  =[]
N = int(input())

graph = []

for i in range(N):
    x, y = [int(s) for s in input().split()]
    graph.append((i, x, y))

sort_x = sorted(graph, key=lambda x: x[1])
sort_y = sorted(graph, key=lambda x: x[2])

edges = []

for i in range(len(sort_x)-1):
    i1, a, b = sort_x[i]
    i2, c, d = sort_x[i+1]
    w = min(abs(a-c), abs(b-d))
    edges.append((i1, i2, w))
    i1, a, b = sort_y[i]
    i2, c, d = sort_y[i+1]
    w = min(abs(a-c), abs(b-d))
    edges.append((i1, i2, w))


for i in range(N+1):
    par.append(i)



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

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

def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        par[x] = y

ans = 0
edges = sorted(edges, key=lambda x: x[2])
for edge in edges:
    if not same(edge[0], edge[1]):
        union(edge[0], edge[1])
        ans += edge[2]
print(ans)