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:
#https://atcoder.jp/contests/abc065/tasks/arc076_b

from heapq import heappush, heappop

def prim_heap(edges, n):
    visited = [False] * n
    heap = []
    start = 0
    for e in edges[start]:
        heappush(heap, e)
    visited[start] = True

    res = 0
    while heap:
        cost, v = heappop(heap)
        if visited[v]:
            continue
        visited[v] = True
        res += cost
        for c,u in edges[v]:
            if visited[u]:
                continue
            heappush(heap, (c,u))
    return res

n = int(input())
edges = []

for i in range(n):
    x,y = map(int,input().split())
    edges.append((x,y))

x = sorted(range(n), key=lambda i:edges[i][0])
y = sorted(range(n), key=lambda i:edges[i][1])
edge_list = [[] for _ in range(n)]
manhattan = lambda a,b: min(abs(a[0] - b[0]), abs(a[1] - b[1]))
for i in range(n):
    if i + 1 < n:
        edge_list[x[i]].append((manhattan(edges[x[i]], edges[x[i+1]]), x[i+1]))
        edge_list[x[i+1]].append((manhattan(edges[x[i]], edges[x[i+1]]), x[i]))
        edge_list[y[i]].append((manhattan(edges[y[i]], edges[y[i+1]]), y[i+1]))
        edge_list[y[i+1]].append((manhattan(edges[y[i]], edges[y[i+1]]), y[i]))

print(prim_heap(edge_list, n))
# print(edge_list)

Submission status: Accepted

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

def main():
    N = int(input())
    rx,ry = [],[]
    _root = []
    for i in range(N):
        a,b = map(int,input().split())
        rx.append((a,i))
        ry.append((b,i))
    
    I = [i for i in range(N)]
    rank = [1 for _ in range(N)]
    def root(x):
        if x == I[x]:
            return x
        I[x] = root(I[x])
        return I[x]
    
    def unite(x,y):
        px,py = root(x),root(y)
        rx,ry = rank[px],rank[py]
        if rx > ry:
            I[py] = px
        else:
            I[px] = py
            if rx == ry:
                rank[py] += 1

    ans = 0
    rx.sort()
    ry.sort()
    for i in range(N-1):
        dx = rx[i+1][0]-rx[i][0]
        dy = ry[i+1][0]-ry[i][0]
        _root.append((dx,rx[i][1],rx[i+1][1]))
        _root.append((dy,ry[i][1],ry[i+1][1]))
        
    _root.sort()
    a = len(_root)
    for i in range(a):
        cost,now,fol = _root[i]
        if (root(now) == root(fol)):
            continue
        ans += cost
        unite(now,fol)
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import heapq
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
p = []
for i in range(N):
  x, y = map(int, input().split())
  p.append((x, y, i))

e = dd(list)
ps = sorted(p, key = lambda x: (x[1], x[0]))
for i in range(N - 1):
  u = ps[i][2]
  v = ps[i + 1][2]
  d = min(abs(p[u][0] - p[v][0]), abs(p[u][1] - p[v][1]))
  e[u].append((v, d))
  e[v].append((u, d))
ps.sort(key = lambda x: (x[0], x[1]))
for i in range(N - 1):
  u = ps[i][2]
  v = ps[i + 1][2]
  d = min(abs(p[u][0] - p[v][0]), abs(p[u][1] - p[v][1]))
  e[u].append((v, d))
  e[v].append((u, d))
#print(e)

class prim:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def MSTcost(self):
    h = []
    visited = [0] * (self.n + 1)
    ks = list(self.e.keys())
    b = pow(10, 10)
    for edge in self.e[ks[0]]:
      heapq.heappush(h, edge[1] * b + edge[0])
    res = 0
    visited[ks[0]] = 1
    while len(h):
      p = heapq.heappop(h)
      p0 = p // b
      p1 = p % b
      if visited[p1]: continue
      visited[p1] = 1
      for q in self.e[p1]:
        if visited[q[0]]:
          continue
        heapq.heappush(h, q[1] * b + q[0])
      res += p0
    return res

pri = prim(N, e)
print(pri.MSTcost())

Submission status: Accepted

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

def main():
    N = int(input())
    x,y = [],[]
    root = [[] for _ in range(N)]
    go = [True for _ in range(N)]
    for i in range(N):
        _x,_y = map(int,input().split())
        x.append((_x,i))
        y.append((_y,i))
        
    x.sort()
    y.sort()
    
    for i in range(N-1):
        dx = x[i+1][0] - x[i][0]
        dy = y[i+1][0] - y[i][0]
        root[x[i][1]].append((dx,x[i+1][1]))
        root[x[i+1][1]].append((dx,x[i][1]))
        root[y[i][1]].append((dy,y[i+1][1]))
        root[y[i+1][1]].append((dy,y[i][1]))
    
    ans = 0    
    queue = root[0]
    heapq.heapify(queue)
    go[0] = False
    while queue:
        cost,following = heapq.heappop(queue)
        if not go[following]:
            continue
        go[following] = False
        for e in root[following]:
            if go[e[1]]:
                heapq.heappush(queue,e)
        ans += cost
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)
        # あるノードを根とする集合に属するノード数
        self.size = [1] * (n+1)
        # あるノードを根とする集合が木かどうか
        self.tree = [True] * (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 x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def is_same(self, x, y):
        """ 同じ集合に属するか判定 """
        return self.find(x) == self.find(y)

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            res = set()
            for i in range(self.n+1):
                res.add(self.find(i))
            # グループ0の分を引いて返却
            return len(res) - 1
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

N = INT()
X = []
Y = []
for i in range(N):
    x, y = MAP()
    X.append((x, i))
    Y.append((y, i))

# xとy個別にソートして、距離の隣り合う頂点間だけ辺を貼る
X.sort()
Y.sort()
edges = []
for i in range(N-1):
    x1, u = X[i]
    x2, v = X[i+1]
    edges.append((x2-x1, u, v))
    y1, u = Y[i]
    y2, v = Y[i+1]
    edges.append((y2-y1, u, v))

# 最小全域木の構築
edges.sort()
uf = UnionFind(N)
ans = 0
for c, a, b in edges:
    if not uf.is_same(a, b):
        uf.union(a, b)
        ans += c
print(ans)

Submission status: Accepted

Solution code:
import heapq


def prim(n, s, edges):
    # n:頂点数, s:スタートノード
    # edges: edgeリスト(cost, 行き先ノード)
    used = [False] * n
    edgelist = []
    for e in edges[s]:
        heapq.heappush(edgelist, e)
    used[s] = True
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]:
            continue
        used[minedge[1]] = True
        for e in edges[minedge[1]]:
            if not used[e[1]]:
                heapq.heappush(edgelist, e)
        res += minedge[0]
    return res


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

edges = [[] for _ in range(N)]
sorted_xy = sorted(XY, key=lambda x: x[1])
for i in range(N-1):
    a = sorted_xy[i][0]
    b = sorted_xy[i+1][0]
    cost = sorted_xy[i+1][1] - sorted_xy[i][1]
    edges[a].append((cost, b))
    edges[b].append((cost, a))
sorted_xy = sorted(XY, key=lambda x: x[2])
for i in range(N-1):
    a = sorted_xy[i][0]
    b = sorted_xy[i+1][0]
    cost = sorted_xy[i+1][2] - sorted_xy[i][2]
    edges[a].append((cost, b))
    edges[b].append((cost, a))
ans = prim(N, 0, edges)
print(ans)

Submission status: Accepted

Solution code:
'''
　 ∧_,,∧    究極奥義「WAがACになーれ！！」
　（`・ω・)つ━☆・*。
　⊂　　 ノ 　　　・゜+.
　 し’´Ｊ　　*・ 
'''
import sys
input = sys.stdin.readline
class UnionFind():
   # 作りたい要素数nで初期化
   # 使用するインスタンス変数の初期化
   def __init__(self, n):
       self.n = n
       # root[x]<0ならそのノードが根かつその値が木の要素数
       # rootノードでその木の要素数を記録する
       self.root = [-1]*(n+1)
       # 木をくっつける時にアンバランスにならないように調整する
       self.rnk = [0]*(n+1)
   # ノードxのrootノードを見つける
   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):
       # 入力ノードのrootノードを見つける
       x = self.Find_Root(x)
       y = self.Find_Root(y)
       # すでに同じ木に属していた場合
       if(x == y):
           return
       # 違う木に属していた場合rnkを見てくっつける方を決める
       elif(self.rnk[x] > self.rnk[y]):
           self.root[x] += self.root[y]
           self.root[y] = x
       else:
           self.root[y] += self.root[x]
           self.root[x] = y
           # rnkが同じ（深さに差がない場合）は1増やす
           if(self.rnk[x] == self.rnk[y]):
               self.rnk[y] += 1
   # xとyが同じグループに属するか判断
   def isSameGroup(self, x, y):
       return self.Find_Root(x) == self.Find_Root(y)
   # ノードxが属する木のサイズを返す
   def Count(self, x):
       return -self.root[self.Find_Root(x)]
n=int(input())
p=[list(map(int,input().split()))+[i] for i in range(n)]
p.sort()
d=[0]*(2*n-2)
for i in range(n-1):
    d[i]=[p[i][2],p[i+1][2],p[i+1][0]-p[i][0]]
p.sort(key=lambda x:x[1])
for i in range(n-1):
    d[i-1+n]=[p[i][2],p[i+1][2],p[i+1][1]-p[i][1]]
d.sort(key=lambda x:x[2])
h = UnionFind(n) 
cost = 0
for i in d:
    if not h.isSameGroup(i[0],i[1]):
        h.Unite(i[0],i[1])
        cost += i[2]
print(cost)

Submission status: Accepted

Solution code:
n = int(input())
xl = []
yl = []
for i in range(n):
    x,y = map(int,input().split())
    xl.append((x,i))
    yl.append((y,i))

xl = sorted(xl)
yl = sorted(yl)

import heapq
al = []
for i in range(n-1):
    al.append((abs(xl[i+1][0] - xl[i][0]), xl[i][1], xl[i+1][1]))
    al.append((abs(yl[i+1][0] - yl[i][0]), yl[i][1], yl[i+1][1]))

heapq.heapify(al)

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

uf = UnionFind(n)

ans = 0
for i in range(n-1):
    while True:
        c, a, b = heapq.heappop(al)
        if not uf.same(a, b):
            ans += c
            uf.union(a,b)
            break

print(ans)

Submission status: Accepted

Solution code:
class UF:
    def __init__(self, N):
        self.uf = [-1]*N
        self.n = N

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

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size(x) > self.size(y): x, y = y, x
        self.uf[y] += self.uf[x]
        self.uf[x] = y
        self.n -= 1

import sys
input = sys.stdin.readline

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

uf = UF(N)

Px = sorted(P, key=lambda p:p[1])
Py = sorted(P, key=lambda p:p[2])

E = []
for i in range(N-1):
    E.append((Px[i+1][1]-Px[i][1], Px[i][0], Px[i+1][0]))
    E.append((Py[i+1][2]-Py[i][2], Py[i][0], Py[i+1][0]))
E = sorted(E)

ans = 0
for c, p1, p2 in E:
    if uf.find(p1)!=uf.find(p2):
        ans += c
        uf.union(p1, p2)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[]
for i in range(n):
    l.append([i]+list(map(int,input().split())))
g = []
l.sort(key=lambda x: x[1])
for i in range(n-1):
    g.append([l[i][0],l[i+1][0],abs(l[i][1]-l[i+1][1])])
l.sort(key=lambda x: x[2])
for i in range(n-1):
    g.append([l[i][0],l[i+1][0],abs(l[i][2]-l[i+1][2])])

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 minimum_spanning_tree(g,n):
#g=list、「始点、終点、辺の重み」
#n=頂点数
    g.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    ret = 0
    for sg in g:
        a,b,c = sg[0],sg[1],sg[2]
        if not uf.same(a,b):
            uf.union(a,b)
            ret += c
    return ret

print(minimum_spanning_tree(g,n))

Submission status: Accepted

Solution code:
N = int(input())
XY = []
for i in range(N):
  x,y = map(int,input().split())
  XY.append((x,y,i))
E = []
XY.sort()
for i in range(N-1):
  E.append((abs(XY[i+1][0] - XY[i][0]),XY[i][2],XY[i+1][2]))
XY = sorted(XY,key=lambda x:x[1])
for i in range(N-1):
  E.append((abs(XY[i+1][1] - XY[i][1]),XY[i][2],XY[i+1][2]))

*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y

def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
    else:
        p[px] = py
    return 1

E.sort()
ans = 0
for c, v, w in E:
    if unite(v, w):
        ans += c
print(ans)

Submission status: Accepted

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

class UnionFind:
    def __init__(self, n):
        self.state = [-1] * n
        # self.size_table = [1] * n
        # cntはグループ数
        # self.cnt = n

    def root(self, u):
        v = self.state[u]
        if v < 0: return u
        self.state[u] = res = self.root(v)
        return res

    def merge(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if ru == rv: return
        du = self.state[ru]
        dv = self.state[rv]
        if du > dv: ru, rv = rv, ru
        if du == dv: self.state[ru] -= 1
        self.state[rv] = ru
        # self.cnt -= 1
        # self.size_table[ru] += self.size_table[rv]
        return

def main():
    n=int(input())
    xx=[]
    yy=[]
    for i in range(n):
        x,y=MI()
        heappush(xx,[x,i])
        heappush(yy,[y,i])
    #print(xx,yy)
    ee=[]
    px,pi=heappop(xx)
    while xx:
        x,i=heappop(xx)
        heappush(ee,[x-px,pi,i])
        pi,px=i,x
    py,pi=heappop(yy)
    while yy:
        y,i=heappop(yy)
        heappush(ee,[y-py,pi,i])
        pi,py=i,y
    #print(ee)
    uf=UnionFind(n)
    cnt=0
    ans=0
    while ee:
        d,u,v=heappop(ee)
        if uf.root(u)==uf.root(v):continue
        uf.merge(u,v)
        ans+=d
        cnt+=1
        if cnt==n-1:break
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
read = sys.stdin.read

N, *xy = map(int, read().split())
xy = np.array(xy, np.int64).reshape(N, 2)
x = xy[:, 0]
y = xy[:, 1]

arg_x = np.argsort(x)
arg_x1 = arg_x[1:]
arg_x2 = arg_x[:-1]

arg_y = np.argsort(y)
arg_y1 = arg_y[1:]
arg_y2 = arg_y[:-1]

edges_x = x[arg_x1] - x[arg_x2]
edges_y = y[arg_y1] - y[arg_y2]

edges = np.concatenate([edges_x, edges_y])
towns_1 = np.concatenate([np.minimum(arg_x1, arg_x2), np.maximum(arg_y1, arg_y2)])
towns_2 = np.concatenate([np.maximum(arg_x1, arg_x2), np.minimum(arg_y1, arg_y2)])

graph = coo_matrix((edges, (towns_1, towns_2)), shape=(N, N)).tocsr()
tree = minimum_spanning_tree(graph, overwrite=True)
answer = int(tree.sum())

print(answer)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
read = sys.stdin.read

N, *xy = map(int, read().split())
xy = np.array(xy, np.int64).reshape(N, 2)
x = xy[:, 0]
y = xy[:, 1]

arg_x = np.argsort(x)
arg_x1 = arg_x[1:]
arg_x2 = arg_x[:-1]

arg_y = np.argsort(y)
arg_y1 = arg_y[1:]
arg_y2 = arg_y[:-1]

edges_x = x[arg_x1] - x[arg_x2]
edges_y = y[arg_y1] - y[arg_y2]

edges = np.concatenate([edges_x, edges_y])
towns_1 = np.concatenate([np.minimum(arg_x1, arg_x2), np.maximum(arg_y1, arg_y2)])
towns_2 = np.concatenate([np.maximum(arg_x1, arg_x2), np.minimum(arg_y1, arg_y2)])

graph = coo_matrix((edges, (towns_1, towns_2)), shape=(N, N))
tree = minimum_spanning_tree(graph, overwrite=True)
answer = int(tree.sum())

print(answer)

Submission status: Accepted

Solution code:
import sys
import numpy as np
read = sys.stdin.read


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if x == y:
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


N, *xy = map(int, read().split())
xy = np.array(xy, np.int64).reshape(N, 2)
x = xy[:, 0]
y = xy[:, 1]

arg_x = np.argsort(x)
arg_y = np.argsort(y)

edges_x = x[arg_x[1:]] - x[arg_x[:-1]]
edges_y = y[arg_y[1:]] - y[arg_y[:-1]]

edges = np.concatenate([edges_x, edges_y])
towns_1 = np.concatenate([arg_x[:-1], arg_y[:-1]])
towns_2 = np.concatenate([arg_x[1:], arg_y[1:]])

arg_edges = np.argsort(edges)
graph = zip(edges[arg_edges].tolist(), towns_1[arg_edges].tolist(), towns_2[arg_edges].tolist())

tree = UnionFind(N)
answer = 0

for d, t1, t2 in graph:
    if tree.isSameGroup(t1, t2):
        continue

    tree.Unite(t1, t2)
    answer += d

print(answer)

Submission status: Accepted

Solution code:
import sys
import numpy as np
read = sys.stdin.read


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if x == y:
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


N, *xy = map(int, read().split())
xy = np.array(xy, np.int64).reshape(N, 2)
x = xy[:, 0]
y = xy[:, 1]

arg_x = np.argsort(x)
arg_y = np.argsort(y)

edges_x = x[arg_x[1:]] - x[arg_x[:-1]]
edges_y = y[arg_y[1:]] - y[arg_y[:-1]]

edges = np.concatenate([edges_x, edges_y])
towns_1 = np.concatenate([arg_x[:-1], arg_y[:-1]])
towns_2 = np.concatenate([arg_x[1:], arg_y[1:]])

arg_edges = np.argsort(edges)
graph = zip(edges[arg_edges], towns_1[arg_edges], towns_2[arg_edges])

tree = UnionFind(N)
answer = 0

for d, t1, t2 in graph:
    if tree.isSameGroup(t1, t2):
        continue

    tree.Unite(t1, t2)
    answer += d

print(answer)

Submission status: Accepted

Solution code:
import sys
import numpy as np
read = sys.stdin.read


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if x == y:
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


N, *xy = map(int, read().split())
xy = np.array(xy, np.int64).reshape(N, 2)

town = np.arange(N)
arg_x = np.argsort(xy[:, 0])
arg_y = np.argsort(xy[:, 1])

edges_x = (xy[arg_x[1:], 0] - xy[arg_x[:-1], 0]).tolist()
town_x = town[arg_x].tolist()
town_x = zip(town_x[1:], town_x[:-1])

edges_y = (xy[arg_y[1:], 1] - xy[arg_y[:-1], 1]).tolist()
town_y = town[arg_y].tolist()
town_y = zip(town_y[1:], town_y[:-1])

edges = list(zip(edges_x, town_x)) + list(zip(edges_y, town_y))
edges.sort()

tree = UnionFind(N)
answer = 0

for d, (t1, t2) in edges:
    if tree.isSameGroup(t1, t2):
        continue

    tree.Unite(t1, t2)
    answer += d

print(answer)

Submission status: Accepted

Solution code:
import sys
import numpy as np
read = sys.stdin.read


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if x == y:
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


N, *xy = map(int, read().split())
xy = np.array(xy, np.int64).reshape(N, 2)

town = np.arange(N)
arg_x = np.argsort(xy[:, 0])
arg_y = np.argsort(xy[:, 1])

edges_x = xy[arg_x[1:], 0] - xy[arg_x[:-1], 0]
town_x = zip(town[arg_x[1:]], town[arg_x[:-1]])
edges_y = xy[arg_y[1:], 1] - xy[arg_y[:-1], 1]
town_y = zip(town[arg_y[1:]], town[arg_y[:-1]])

edges = list(zip(edges_x, town_x)) + list(zip(edges_y, town_y))
edges.sort()

tree = UnionFind(N)
answer = 0

for d, (t1, t2) in edges:
    if tree.isSameGroup(t1, t2):
        continue

    tree.Unite(t1, t2)
    answer += d

print(answer)

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

    append = xy.append
    for i in range(N):
        append((i,x[i],y[i]))

    x_xy = sorted(xy, key= lambda x:x[1])
    y_xy = sorted(xy, key= lambda x:x[2])

    append = edges.append
    for i in range(N-1):
        cur = x_xy[i]
        next = x_xy[i+1]
        append((next[1]-cur[1],next[0],cur[0]))
        cur = y_xy[i]
        next = y_xy[i+1]
        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()