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 time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    class UnionFindTree:
        def __init__(self, num_of_elm):
            '''
            0 ... num_of_elem - 1 まで数字で表される (0-index) グループを管理する union find tree を作成する (O(n))
            '''
            self.n = num_of_elm
            self.table = [i for i in range(self.n)]    # table[ind] は ind の親の index を表す。ind == table[ind] の時そのグループの root である。
            self.rank = [0] * self.n    # root となる ind について rank[ind] はその木の深さを表す。それ以外の ind については意味を持たない。
            self.group_size = [1] * self.n    # root となる ind について group_size[ind] はそのグループに属するメンバの個数を表す。それ以外の ind については意味を持たない。
        
        def _find_set(self, x):
            '''
            x の属するグループ番号を O(α(n)) で求める
            '''
            parent = self.table[x]
            if x == parent:
                return x
            else:
                root = self._find_set(parent)
                # 経路圧縮
                self.table[x] = root
                return root
        
        def is_same(self, x, y):
            '''
            x と y が同じグループに属するか O(α(n)) で判定する
            '''
            return self._find_set(x) == self._find_set(y)
    
        def union(self, x, y):
            '''
            x と y の属するグループを O(α(n)) で統合する
            '''
            shallow_root = self._find_set(x)
            deep_root = self._find_set(y)
            if self.rank[shallow_root] > self.rank[deep_root]:
                shallow_root, deep_root = deep_root, shallow_root
            # そもそも同一グループだった時
            if shallow_root == deep_root:
                return False
            # グループが異なるので union
            else:
                self.table[shallow_root] = deep_root
                self.group_size[deep_root] += self.group_size[shallow_root]
                # 深さが等しかったときはつけ加えられた側の rank をインクリメントする
                if self.rank[shallow_root] == self.rank[deep_root]:
                    self.rank[deep_root] += 1
                return True
    
        def akin_num(self, x):
            '''
            x の属するグループのサイズを O(1) で計算する
            '''
            x_root = self._find_set(x)
            return self.group_size[x_root]
    
        def print_group_id(self):
            print([self._find_set(x) for x in self.table])

    
    def kruskal(edges, n):
        uf = UnionFindTree(n)
        total_cost = 0
        edges.sort(key=itemgetter(2))
        for e in edges:
            u, v, weight = e
            if uf.union(u, v):
                total_cost += weight
        return total_cost


    n = ii()
    appeared = set()
    L = []
    cnt = 0
    for _ in range(n):
        x, y = mi()
        if (x, y) in appeared:    # 同じ座標の点はここで弾いておく
            n -= 1
            continue
        L.append([cnt, x, y])
        appeared.add((x, y))
        cnt += 1
    
    edges = []
    s = set()
    L.sort(key=itemgetter(1))    # x でソート
    for j in range(1, n):
        u, v = L[j][0], L[j-1][0]    # ind of points
        u, v = min(u, v), max(u, v)
        dist = min(abs(L[j][1] - L[j-1][1]), abs(L[j][2] - L[j-1][2]))
        s.add((u, v))
        edges.append((u, v, dist))
    L.sort(key=itemgetter(2))    # y でソート
    for j in range(1, n):
        u, v = L[j][0], L[j-1][0]    # ind of points
        u, v = min(u, v), max(u, v)
        # 重複はチェック
        if (u, v) not in s:
            dist = min(abs(L[j][1] - L[j-1][1]), abs(L[j][2] - L[j-1][2]))
            edges.append((u, v, dist))
    
    print(kruskal(edges, n))
    




if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Gx=sorted(G,key=lambda x:x[0])
Gy=sorted(G,key=lambda x:x[1])

newG=[]
for i in range(N-1):
    now=Gx[i]
    next=Gx[i+1]
    dist=abs(now[0]-next[0])
    newG.append((dist,now[2],next[2]))

for i in range(N-1):
    now=Gy[i]
    next=Gy[i+1]
    dist=abs(now[1]-next[1])
    newG.append((dist,now[2],next[2]))

newG.sort()

uf=UnionFind(N)
count=N
ans=0
for c,i,j in newG:
    if count==0:
        break

    if not uf.same(i,j):
        ans+=c
        uf.union(i,j)
        count-=1

print(ans)

Submission status: Accepted

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

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

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

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

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

edges = []

sort_x = sorted(coordinates, key=lambda x: x[1])
for i in range(N-1):
  u,v = sort_x[i][0], sort_x[i+1][0]
  edges.append([u,v,abs(sort_x[i][1] - sort_x[i+1][1])])

sort_y = sorted(coordinates, key=lambda x: x[2])
for i in range(N-1):  
  u,v = sort_y[i][0], sort_y[i+1][0]
  edges.append([u,v,abs(sort_y[i][2] - sort_y[i+1][2] )])

edges.sort(key=lambda x: x[2])
uf = UF(N)
res = 0
for u,v,c in edges:
  if not uf.same(u,v):
    uf.union(u,v)
    res += c

print(res)

Submission status: Accepted

Solution code:
from operator import itemgetter


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * 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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        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]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same(self, x, y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False


def kruskal(n, edges):
    uf = UnionFind(n)
    edges.sort()
    res = 0
    for d, s, t in edges:
        if not uf.same(s, t):
            uf.unite(s, t)
            res += d
    return res

n = int(input())

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

edges = set()
for key in [itemgetter(1), itemgetter(2)]:
    xy.sort(key = key)
    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))
        edges.add((d, i1, i2))

edges = list(edges)
print(kruskal(n, edges))

Submission status: Accepted

Solution code:
n = int(input())
plots = []
for i in range(n):
    x, y = map(int, input().split())
    plots.append((x, y, i))
edges = []
plots.sort(key=lambda x: x[0])
for k in range(n-1):
    x0, _, i = plots[k]
    x1, _, j = plots[k+1]
    edges.append((x1 - x0, i, j))

plots.sort(key=lambda x: x[1])
for k in range(n-1):
    _, y0, i = plots[k]
    _, y1, j = plots[k+1]
    edges.append((y1 - y0, i, j))



par = [i for i in range(n)]
size = [1 for _ in range(n)]
rank = [0 for _ in range(n)]
def find(x):  # 木の根を求める
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] > rank[y]:
        par[y] = x
        size[x] += size[y]
    else:
        par[x] = y
        size[y] += size[x]
        if rank[x] == rank[y]:
            rank[y] += 1
def same(x, y):
    return find(x) == find(y)


def kruskal():
    edges.sort()

    res = 0
    for i in range(len(edges)):
        cost, u, v = edges[i]
        if not same(u, v):
            unite(u, v)
            res += cost

    return res

print(kruskal())

Submission status: Accepted

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

from itertools import permutations
n = int(input())
list_XY = []
list_CO = []
for i in range(n):
    x, y = map(int, input().split())
    list_XY.append([x, y, i])

list_XY.sort(key=lambda x:x[0])
for i in range(n-1):
    list_CO.append([list_XY[i][2], list_XY[i+1][2], abs(list_XY[i][0]-list_XY[i+1][0])])

list_XY.sort(key=lambda x:x[1])
for i in range(n-1):
    list_CO.append([list_XY[i][2], list_XY[i+1][2], abs(list_XY[i][1]-list_XY[i+1][1])])

list_CO.sort(key=lambda x:x[2])
uf = UnionFind(n)
ans = 0

for i, j, cost in list_CO:
    if not uf.same(i, j):
        uf.union(i, j)
        ans += cost
    if uf.size(0) == n:
        break

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
        else:
            self.parents[xRoot] = yRoot
            if self.size[xRoot] == self.size[yRoot]:
                self.size[yRoot]+=1

N = int(input())
edges = []
nodes = []
for i in range(N):
    x,y = map(int,input().split())
    nodes.append((i,x,y))
nodes.sort(key=lambda x: x[1])
for i in range(1,N):
    w = nodes[i][1]-nodes[i-1][1]
    edges.append((w,nodes[i][0],nodes[i-1][0]))
nodes.sort(key=lambda x: x[2])
for i in range(1,N):
    w = nodes[i][2] - nodes[i-1][2]
    edges.append((w,nodes[i][0],nodes[i-1][0]))
edges.sort()
tree = UnionFind(N)
cost = 0
for w,a,b in edges:
    if tree.find(a) != tree.find(b):
        tree.unite(a,b)
        cost += w
print(cost)

Submission status: Accepted

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


n = int(input())
graphx = []
graphy = []

for i in range(n):
    x,y = map(int,input().split())
    graphx.append((x,y,i))
    graphy.append((x,y,i))
graphx = sorted(graphx, key=lambda x:x[0])
graphy = sorted(graphy, key=lambda x:x[1])
graph = []


for k in range(n-1):
    i,j = graphx[k][2], graphx[k+1][2]
    x0,x1 = graphx[k][0],graphx[k+1][0]
    m = abs(x0-x1)
    graph.append((m,i,j))

for k in range(n-1):
    i,j = graphy[k][2], graphy[k+1][2]
    y0,y1 = graphy[k][1],graphy[k+1][1]
    m = abs(y0-y1)
    graph.append((m,i,j))


graph.sort()
#print(graph)

ans = 0
uf = UnionFind(n)
for c,i,j in graph:
    if not uf.same(i,j):
        ans += c
        uf.union(i,j)
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix

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

length, frm, to = [], [], []
path_set = set()


def path(axis):
    A.sort(key=lambda x: x[axis])
    for i in range(N - 1):
        if (A[i][0], A[i + 1][0]) in path_set:
            continue
        length.append(min(abs(A[i][1] - A[i + 1][1]),
                          abs(A[i][2] - A[i + 1][2])))
        frm.append(A[i][0])
        to.append(A[i + 1][0])
        path_set.add((A[i][0], A[i + 1][0]))


path(1)
path(2)
matr = csr_matrix((length, (frm, to)), shape=(N, N))

T = minimum_spanning_tree(matr).astype(int)
print(sum(T.data))

Submission status: Accepted

Solution code:
#最小全域木問題、プリム法
from heapq import *
def solve():
    N = int(input())
    A = [list(map(int, input().split()))+[i] for i in range(N)]
    edge = [[] for _ in range(N)]
    A.sort()
    for i in range(N-1):
        w = A[i+1][0]-A[i][0]
        edge[A[i][2]].append((w,A[i+1][2]))
        edge[A[i+1][2]].append((w,A[i][2]))
    A.sort(key=lambda x:x[1])
    for i in range(N-1):
        w = A[i+1][1]-A[i][1]
        edge[A[i][2]].append((w,A[i+1][2]))
        edge[A[i+1][2]].append((w,A[i][2]))
    bridges = []
    heapify(bridges)
    used = [False]*N
    used[0] = True
    ans = 0
    for w,v in edge[0]:
        heappush(bridges,(w,v))
    while len(bridges)>0:
        w,v = heappop(bridges)
        if used[v]==False:
            ans += w
            used[v] = True
            for w,u in edge[v]:
                if used[u]==False:
                    heappush(bridges,(w,u))
    return ans
print(solve())

Submission status: Accepted

Solution code:
#最小全域木問題、プリム法
from heapq import *
def solve():
    N = int(input())
    A = [list(map(int, input().split()))+[i] for i in range(N)]
    edge = [[] for _ in range(N)]
    A.sort()
    for i in range(N-1):
        w = min(abs(A[i+1][0]-A[i][0]),abs(A[i+1][1]-A[i][1]))
        edge[A[i][2]].append((w,A[i+1][2]))
        edge[A[i+1][2]].append((w,A[i][2]))
    A.sort(key=lambda x:x[1])
    for i in range(N-1):
        w = min(abs(A[i+1][0]-A[i][0]),abs(A[i+1][1]-A[i][1]))
        edge[A[i][2]].append((w,A[i+1][2]))
        edge[A[i+1][2]].append((w,A[i][2]))
    bridges = []
    heapify(bridges)
    used = [False]*N
    used[0] = True
    ans = 0
    for w,v in edge[0]:
        heappush(bridges,(w,v))
    while len(bridges)>0:
        w,v = heappop(bridges)
        if used[v]==False:
            ans += w
            used[v] = True
            for w,u in edge[v]:
                if used[u]==False:
                    heappush(bridges,(w,u))
    return ans
print(solve())

Submission status: Accepted

Solution code:
import sys;sys.setrecursionlimit(10**9)
class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
    self.siz=n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
    self.siz-=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]
  def size(self):
    return self.siz

n=int(input())
xy=[list(map(int,input().split()))+[i]for i in range(n)]
xy.sort()
edge=[]
for j in range(1,n):
  sx,sy,si=xy[j-1]
  tx,ty,ti=xy[j]
  edge.append((min(abs(sx-tx),abs(sy-ty)),si,ti))
xy.sort(key=lambda x:x[1])
for j in range(1,n):
  sx,sy,si=xy[j-1]
  tx,ty,ti=xy[j]
  edge.append((min(abs(sx-tx),abs(sy-ty)),si,ti))
u=UnionFind(n)
ans=0
edge.sort()
for c,x,y in edge:
  if u.root_same(x,y):continue
  u.unite(x,y)
  ans+=c
print(ans)

Submission status: Accepted

Solution code:
class Kruskal():
    def __init__(self,n):
        self.e = []
        self.par = [i for i in range(n+1)]  #親のノード番号
        self.rank = [0]*(n+1)
    def add(self,u,v,d):  #クラスカル法で考えるのは無向グラフ
        self.e.append([u,v,d])
    def find(self,x):  #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):  #x,yが同じグループか否か
        return self.find(x) == self.find(y)
    def unite(self,x,y):  #x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1
    def Kruskal(self):
        edges = sorted(self.e,key=lambda x: x[2])  #距離でソート
        a = 0
        for e in edges:
            if not self.same_check(e[0],e[1]):
                self.unite(e[0],e[1])
                a += e[2]
        return a

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

G = Kruskal(N)

X = []
Y = []
for i in range(N):
    X.append((A[i][0], i))
    Y.append((A[i][1], i))

X = sorted(X)
Y = sorted(Y)

# 辞書順で隣り合うものだけ考えれば良い

for i in range(N - 1):
    G.add(X[i][1], X[i + 1][1], X[i + 1][0] - X[i][0])
    G.add(Y[i][1], Y[i + 1][1], Y[i + 1][0] - Y[i][0])

print(G.Kruskal())

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from operator import itemgetter

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


class UnionFind:
    # Reference: https://note.nkmk.me/python-union-find/
    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)


N = int(input())
P = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    P[i] = (i, x, y)

edges = []
for i in (1, 2):
    P.sort(key=itemgetter(i))
    for j in range(N - 1):
        edges.append((P[j][0], P[j + 1][0], P[j + 1][i] - P[j][i]))

edges.sort(key=itemgetter(2))
uf = UnionFind(N)
ans = 0
cities = 1
for i, j, c in edges:
    if not uf.same(i, j):
        uf.union(i, j)
        ans += c
        cities += 1
        if cities == N:
            break

print(ans)

Submission status: Accepted

Solution code:

import numpy as np
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix
from operator import itemgetter
def resolve():
    N = int(input())
    XY = [[i] + [int(x) for x in input().split()] for i in range(N)]

    G = set()
    for key in [itemgetter(1), itemgetter(2)]:
        XY.sort(key=key)
        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))
            G.add((i1, i2, d))    

    A, B, W = zip(*G)
    csr = csr_matrix((W, (A, B)), shape=(N, N))
    mst = minimum_spanning_tree(csr).astype(int)
    print(mst.sum())

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

# n個の要素を0~N-1で管理
class UnionFind():
    # 各要素の親要素の番号を格納するリスト
    # 要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    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

    # 要素xが属するグループのサイズ（要素数）を返す
    def size(self, x):
        return -self.parents[self.find(x)]

    # 要素x, yが同じグループに属するかどうかを返す
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    # 要素xが属するグループに属する要素をリストで返す
    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()}

    # ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す (print()での表示用)
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def resolve():
    N = int(input())
    X = []
    Y = []
    # 町のナンバーも付ける
    for i in range(N):
        x, y = map(int, input().split())
        X.append((i, x))
        Y.append((i, y))

    # 短い距離にある街をつなげば良いのでソートする
    X.sort(key=lambda x: x[1])
    Y.sort(key=lambda x: x[1])

    # コストを計算しグラフを作成
    G = []
    for i in range(1, N):
        a, x1 = X[i - 1]
        b, x2 = X[i]
        G.append((a,b,x2-x1))
        a, y1 = Y[i - 1]
        b, y2 = Y[i]
        G.append((a, b, y2 - y1))

    # クラシカル法で最小全域木
    ans = 0
    uf = UnionFind(N)
    G.sort(key=lambda x: x[2])
    for a, b, w in G:
        if not uf.is_same(a, b):
            uf.union(a, b)
            ans += w
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

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 kruskal(es, V):
    es.sort(key=lambda x:x[2])
    uf = UnionFind(V)
    res = 0
    for e in es:
        if not uf.same(e[0], e[1]):
            uf.union(e[0], e[1])
            res += e[2]
    return res

def resolve():
    N = I()
    xy = [LI() for _ in range(N)]

    # 辺の候補は、xyそれぞれでソートした隣同士の点の間のみに絞れる
    xy_x_asc = sorted(enumerate(xy), key=lambda x: x[1][0])
    xy_y_asc = sorted(enumerate(xy), key=lambda x: x[1][1])
    edge = []
    for i in range(N-1):
        xc = xy_x_asc[i][1][0]
        yc = xy_x_asc[i][1][1]
        xyc_num = xy_x_asc[i][0]
        xn = xy_x_asc[i+1][1][0]
        yn = xy_x_asc[i+1][1][1]
        xyn_num = xy_x_asc[i+1][0]
        edge.append([xyc_num, xyn_num, abs(xn-xc)])
    for i in range(N-1):
        xc = xy_y_asc[i][1][0]
        yc = xy_y_asc[i][1][1]
        xyc_num = xy_y_asc[i][0]
        xn = xy_y_asc[i+1][1][0]
        yn = xy_y_asc[i+1][1][1]
        xyn_num = xy_y_asc[i+1][0]
        edge.append([xyc_num, xyn_num, abs(yn-yc)])

    # print(edge)
    mst_cost = kruskal(edge, N)
    print(mst_cost)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

lx = sorted(l)
ly = sorted(l, key=lambda x: x[1])

e = []
for i in range(n-1):
    e.append([lx[i+1][0]-lx[i][0],lx[i+1][2],lx[i][2]])
    e.append([ly[i+1][1]-ly[i][1],ly[i+1][2],ly[i][2]])


class Unionfind:
    
    def __init__(self,n):
        self.uf = [-1]*n

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

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

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

    def size(self,x):
        x = self.find(x)
        return -self.uf[x]
s = set()
u = Unionfind(n)
count = 0
e.sort()
for i in e:
    if not u.same(i[1],i[2]):
        u.union(i[1],i[2])
        s.add(i[1])
        s.add(i[2])
        count += i[0]
print(count)