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:
from heapq import heappush, heappop
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.size = [1]*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 unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      self.size[y] += self.size[x]
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
      self.size[x] += self.size[y]
    else:
      self.par[y] = x
      self.size[x] += self.size[y]
      self.rank[x] += 1 
  def same(self, x, y):
    return self.find(x)==self.find(y)
  
N = int(input())
X = []
Y = []
for i in range(N):
  x, y = map(int, input().split())
  X += [(x,y,i)]
  Y += [(x,y,i)]
X.sort()
Y.sort(key=lambda x:x[1])
hq = []
for i in range(N-1):
  x1, y1, i1 = X[i]
  x2, y2, i2 = X[i+1]
  heappush(hq, (x2-x1,i1,i2))
  x1, y1, i1 = Y[i]
  x2, y2, i2 = Y[i+1]
  heappush(hq, (y2-y1,i1,i2))

u  = UnionFind(N)
cnt = 1
ans = 0
while cnt<N:
  c, i1, i2 = heappop(hq)
  if u.same(i1,i2):
    continue
  ans += c
  cnt += 1
  u.unit(i1,i2)
print(ans)

Submission status: Accepted

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

N, *XY = map(int, open(0).read().split())

XY = list(enumerate(zip(*[iter(XY)] * 2)))
X = sorted(XY, key=lambda x: x[1][0])
Y = sorted(XY, key=lambda x: x[1][1])

E = {(i1, i2, min(abs(x1 - x2), abs(y1 - y2))) for (i1, (x1, y1)), (i2, (x2, y2)) in zip(X, X[1:])} \
  | {(i1, i2, min(abs(x1 - x2), abs(y1 - y2))) for (i1, (x1, y1)), (i2, (x2, y2)) in zip(Y, Y[1:])}

R, C, V = zip(*E)
G = csr_matrix((V, (R, C)), shape=(N, N))

ans = minimum_spanning_tree(G, overwrite=True).astype(int).sum()
print(ans)

Submission status: Accepted

Solution code:
import heapq as hq
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0]*size
    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def unite(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
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
N = int(input())
ls = []
rs = []
ind = 0
inds = dict()
for _ in range(N):
    x,y = map(int,input().split())
    if (x,y) not in inds.keys():
        ls.append((x,y))
        rs.append((y,x))
        inds[(x,y)] = ind
        ind += 1
N = ind
ls.sort()
rs.sort()
uf = UnionFind(N)

edges = []
for i in range(N-1):
    x = ls[i][0]
    a = ls[i+1][0]
    y = ls[i][1]
    b = ls[i+1][1]
    d = min(abs(x-a), abs(y-b))
    edges.append((d,(x,y),(a,b)))
    x = rs[i][1]
    a = rs[i+1][1]
    y = rs[i][0]
    b = rs[i+1][0]
    d = min(abs(x-a), abs(y-b))
    edges.append((d,(x,y),(a,b)))
edges.sort(key=lambda x:x[0])
ans = 0
for d,i,j in edges:
        # 閉路ができない場合追加する
        if not uf.same(inds[i],inds[j]):
            uf.unite(inds[i],inds[j])
            ans += d
print(ans)

Submission status: Accepted

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

def unite(u, v):
    u = root(u)
    v = root(v)
    if u == v:
        return
    if rank[u] < rank[v]:
        u, v = v, u
    par[v] = u
    if rank[u] == rank[v]:
        rank[u] += 1

def same(u, v):
    return root(u) == root(v)

def kruskal(edges):
    heapq.heapify(edges)
    res = 0
    while edges:
        w, u, v = heapq.heappop(edges)
        if same(u, v):
            continue
        unite(u, v)
        res += w
    return res

import heapq
N = int(input())
X = [() for _ in range(N)]
Y = [() for _ in range(N)]
for i in range(N):
    x, y = map(int, input().split())
    X[i] = (x, i)
    Y[i] = (y, i)
X = sorted(X)
Y = sorted(Y)
E = []
heapq.heapify(E)
for i in range(N-1):
    x, v = X[i]
    nx, nv = X[i+1]
    heapq.heappush(E, (nx-x, v, nv))
    y, u = Y[i]
    ny, nu = Y[i+1]
    heapq.heappush(E, (ny-y, u, nu))

par = list(range(N))
rank = [0] * N
print(kruskal(E))

Submission status: Accepted

Solution code:
import heapq
def prim(edges):
    visited = [False] * N
    visited[0] = True
    hq = [e for e in E[0]]
    heapq.heapify(hq)
    res = 0
    while len(hq) != 0:
        w, v = heapq.heappop(hq)
        if visited[v]:
            continue
        visited[v] = True
        res += w
        for z, u in E[v]:
            if visited[u]:
                continue
            heapq.heappush(hq, (z, u))
    return res


N = int(input())
X = [() for _ in range(N)]
Y = [() for _ in range(N)]
for i in range(N):
    x, y = map(int, input().split())
    X[i] = (x, i)
    Y[i] = (y, i)
X = sorted(X)
Y = sorted(Y)
E = [[] for _ in range(N)]
for i in range(N-1):
    x, v = X[i]
    nx, nv = X[i+1]
    E[v].append((nx-x, nv))
    E[nv].append((nx-x, v))
    y, u = Y[i]
    ny, nu = Y[i+1]
    E[u].append((ny-y, nu))
    E[nu].append((ny-y, u))

print(prim(E))

Submission status: Accepted

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for _ in range(n)]

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

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

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

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

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

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

def kruskal(e,n):
    l = []
    for v in range(n):
        for u,c in e[v]:
            l.append((c,v,u))
    l.sort()

    uf = UnionFind(n)
    cost = 0
    res = []
    for c,v,u in l:
        if uf.same(v,u):
            continue
        res.append((v,u,c))
        cost += c
        uf.unite(v,u)
    return res,cost


n = int(input())
e = [[] for _ in range(n)]

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

ixy.sort(key=itemgetter(1,2))
for i in range(n-1):
    v,a,b = ixy[i]
    u,c,d = ixy[i+1]
    e[v].append((u,min(abs(a-c),abs(b-d))))

ixy.sort(key=itemgetter(2,1))
for i in range(n-1):
    v,a,b = ixy[i]
    u,c,d = ixy[i+1]
    e[v].append((u,min(abs(a-c),abs(b-d))))

r,cost = kruskal(e,n)
print(cost)

Submission status: Accepted

Solution code:
#最小領域木
#ABC065D - Built?
#https://atcoder.jp/contests/abc065/tasks/arc076_b

#自己考察TLE

import sys

n = int(input())
cad = []
lst = []
for i in range(n):
    x, y =  list(map(int,input().split()))
    lst.append([x,y,i])
lstx = lst.sort(key = lambda x: x[0])
for i in range(n-1):
    cad.append([lst[i+1][0] - lst[i][0],lst[i+1][2],lst[i][2]])
lsty = lst.sort(key = lambda x: x[1])
for i in range(n-1):
    cad.append([lst[i+1][1] - lst[i][1],lst[i+1][2],lst[i][2]])

cad.sort()

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

h = UnionFind(n)
cost = 0
count = 0
for i in range(len(cad)):
    a = cad[i][1]
    b = cad[i][2]
    c = cad[i][0]
    if  not h.same(a,b):
        h.union(a,b)
        cost += c
        count += 1
    if count == n-1:
        print(cost)
        sys.exit()

Submission status: Accepted

Solution code:
import sys
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)

# 最小全域木
# プリム法 #
# 部分木から、最小コストの辺を貪欲に追加

# Kruskal法 #
# クラスカル法 #
# 辺でソートして、最小コストの辺から、ループにならないよう貪欲に追加
# UnionFindを使う


N = int(input())

# x,yでそれぞれソート
POINT_x = []
POINT_y = []
for _ in range(N):
    x, y = map(int, input().split())
    POINT_x.append((x, y))
    POINT_y.append((x, y))

POINT_x = sorted(POINT_x, key=lambda x: x[0])
POINT_y = sorted(POINT_y, key=lambda x: x[1])

EDGE = defaultdict(list)
for i in range(N):
    p = POINT_x[i]

    if i != 0:
        prev = POINT_x[i-1]
        EDGE[p].append((abs(p[0]-prev[0]), prev))

    if i != N-1:
        nxt = POINT_x[i+1]
        EDGE[p].append((abs(p[0]-nxt[0]), nxt))

for i in range(N):
    p = POINT_y[i]

    if i != 0:
        prev = POINT_y[i-1]
        EDGE[p].append((abs(p[1]-prev[1]), prev))

    if i != N-1:
        nxt = POINT_y[i+1]
        EDGE[p].append((abs(p[1]-nxt[1]), nxt))


INF = 10 ** 12
mincost = [INF] * N
used = defaultdict(lambda: False)

point = POINT_x[0]
used[point] = True
q = []
ans = 0

for e in EDGE[point]:
    heapq.heappush(q, e)

while(True):
    update = False
    for _ in range(len(q)):
        cost, point = heapq.heappop(q)
        if used[point]:
            continue

        update = True
        ans += cost
        used[point] = True

        for e in EDGE[point]:
            if not used[e[1]]:
                heapq.heappush(q, e)

    if not update:
        break

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)
from collections import defaultdict
# d = defaultdict(list)

from itertools import combinations
# comb = combinations(range(N), 2)

from functools import reduce
from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.N = n
        self.parent = list(range(n))
        self.rank = [1 for _ in range(n)]

    def findRoot(self, i):
        if self.parent[i] == i:  # 親が自分ならroot
            return i
        else:
            self.parent[i] = self.findRoot(self.parent[i])  # 親をrootに付け替える
            return self.parent[i]

    def unite(self, i, j):
        i_root = self.findRoot(i)
        j_root = self.findRoot(j)
        if i_root == j_root:
            return

        if self.rank[i_root] > self.rank[j_root]:  # ランクが高い方を親にする。
            self.parent[j_root] = i_root
        elif self.rank[i_root] == self.rank[j_root]:
            self.parent[j_root] = i_root
            self.rank[i_root] += 1
        else:
            self.parent[i_root] = j_root

        return i

    def isSame(self, i, j):
        return self.findRoot(i) == self.findRoot(j)

    def setGroup(self, elements):
        reduce(self.unite, elements)

    def getElementCount(self):  # 要素ごとにそれが属してる集合の要素数を取る
        roots = [self.findRoot(i) for i in range(self.N)]
        counts = Counter(roots)
        return [counts[r] for r in roots]

    def getRootCount(self):  # ルートごとにそれが属してる集合の要素数を取る
        roots = [self.findRoot(i) for i in range(self.N)]
        counts = Counter(roots)
        return counts


def resolve():
    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    # N, D = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # h_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    grid = [[int(x) for x in sys.stdin.readline().split()] + [i]
            for i in range(N)]  # int grid

    logger.debug('{}'.format([]))

    edge_list = []
    # x でソート
    grid = sorted(grid, key=lambda xy: xy[0])
    for i in range(N - 1):
        xi, yi, vi = grid[i]
        xj, yj, vj = grid[i + 1]
        edge_list.append((min(abs(xi - xj), abs(yi - yj)), vi, vj))

    # y でソート
    grid = sorted(grid, key=lambda xy: xy[1])

    for i in range(N - 1):
        xi, yi, vi = grid[i]
        xj, yj, vj = grid[i + 1]
        edge_list.append((min(abs(xi - xj), abs(yi - yj)), vi, vj))

    edge_list = sorted(edge_list)

    union_find = UnionFind(N)

    total_cost = 0
    for edge in edge_list:
        cost, i, j = edge
        if not union_find.isSame(i, j):
            union_find.unite(i, j)
            total_cost += cost

    print(total_cost)


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
1 5
3 9
7 8"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """6
8 3
4 9
12 19
18 1
13 5
7 6"""
        output = """8"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """2
0 0
0 0"""
        output = """0"""
        self.assertIO(input, output)

Submission status: Accepted

Solution code:
# D - Built?

import sys

class UnionFind(object):
    def __init__(self, n=1):
        self.root = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

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

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.root[y] = x

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

# edges : [[start, end, edge_weight], ...]
def kruskal(max_v, edges):
    uf = UnionFind(max_v)
    sum_cost = 0
    edges.sort(key = lambda x: x[2])
    for e in edges:
        if not uf.is_same_root(e[0], e[1]):
            uf.unite(e[0], e[1])
            sum_cost += e[2]
    return sum_cost


N = int(sys.stdin.buffer.readline())
xyi = []
for i in range(N):
    x, y = map(int, sys.stdin.buffer.readline().split())
    xyi.append([x,y,i])

edges = []
xyi.sort(key = lambda x:x[0])
for j in range(N):
    if 0 < j:
        edges.append([xyi[j-1][2], xyi[j][2], xyi[j][0]-xyi[j-1][0]])
    if j < N-1:
        edges.append([xyi[j][2], xyi[j+1][2], xyi[j+1][0]-xyi[j][0]])

xyi.sort(key=lambda x: x[1])
for j in range(N):
    if 0 < j:
        edges.append([xyi[j-1][2], xyi[j][2], xyi[j][1]-xyi[j-1][1]])
    if j < N-1:
        edges.append([xyi[j][2], xyi[j+1][2], xyi[j+1][1]-xyi[j][1]])

print(kruskal(N, edges))

Submission status: Accepted

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

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

dist = []

XY.sort()
for i in range(N - 1):
  dist.append((abs(XY[i][0] - XY[i + 1][0]), (XY[i][2], XY[i + 1][2])))
XY.sort(key = lambda x: x[1])
for i in range(N - 1):
  dist.append((abs(XY[i][1] - XY[i + 1][1]), (XY[i][2], XY[i + 1][2])))
dist.sort()

root = [i for i in range(N + 1)]
comp_size = [1] * (N+1)
 
def root_find(x):
  if x == root[x]:
    return x
  else:
    z = root_find(root[x])
    root[x] = z
    return z

def merge(x, y):
  rx = root_find(x)
  ry = root_find(y)
  sx = comp_size[rx]
  sy = comp_size[ry]
  if rx != ry:
    if sx >= sy:
      root[ry] = rx
      comp_size[rx] = sx + sy
    else:
      root[rx] = ry
      comp_size[ry] = sx + sy
      
answer = 0
for d, (a, b) in dist:
  if root_find(a) != root_find(b):
    merge(a, b)
    answer += d

print(answer)

Submission status: Accepted

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

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

dist = []

XY.sort()
for i in range(N - 1):
  dist.append((abs(XY[i][0] - XY[i + 1][0]), (XY[i][2], XY[i + 1][2])))
XY.sort(key = lambda x: x[1])
for i in range(N - 1):
  dist.append((abs(XY[i][1] - XY[i + 1][1]), (XY[i][2], XY[i + 1][2])))
dist.sort()

root = [i for i in range(N + 1)]
comp_size = [1] * (N+1)
 
def root_find(x):
  y = root[x]
  if x == y:
    return x
  else:
    z = root_find(y)
    root[x] = z
    return z

def merge(x, y):
  rx = root_find(x)
  ry = root_find(y)
  sx = comp_size[rx]
  sy = comp_size[ry]
  if rx != ry:
    if sx >= sy:
      root[ry] = rx
      comp_size[rx] = sx + sy
    else:
      root[rx] = ry
      comp_size[ry] = sx + sy
      
answer = 0
for d, (a, b) in dist:
  if root_find(a) != root_find(b):
    merge(a, b)
    answer += d

print(answer)

Submission status: Accepted

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

def find_parent(x):
    y=parent[x]
    if y<0:
        return x
    parent[x]=find_parent(y)
    return parent[x]

def connect(a,b):
    c=find_parent(a)
    d=find_parent(b)
    if c==d:
        return
    if parent[c]<parent[d]:
        parent[c]+=parent[d]
        parent[d]=c
    else:
        parent[d]+=parent[c]
        parent[c]=d
    return

N=int(input())
X=[]
Y=[]
for i in range(N):
    x,y=map(int,input().split())
    X.append([x,i])
    Y.append([y,i])
inf=float("inf")

X.sort()
Y.sort()
edge=[]
for i in range(1,N):
    edge.append([X[i][0]-X[i-1][0],X[i-1][1],X[i][1]])
    edge.append([Y[i][0]-Y[i-1][0],Y[i-1][1],Y[i][1]])
edge.sort()
parent=[-1]*N

ans=0
for l,a,b in edge:
    if find_parent(a)==find_parent(b):
        continue
    else:
        ans+=l
        connect(a,b)

print(ans)

Submission status: Accepted

Solution code:
import heapq
N = int(input())
town = []
for i in range(N):
    x, y = map(int, input().split())
    town.append((x, y, i))

uf = [i for i in range(N)]      #uf[i]==iであれば根

def root(x):
    if x == uf[x]:
        return x
    else:
        r = root(uf[x])
        uf[x] = r
        return r

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

def unite(x, y):
    x = root(x)
    y = root(y)
    if x==y:
        return
    uf[x] = y
    return

road = []
town.sort() #x座標でソート O(NlogN + N)
for i in range(N-1):
    x1, _, ind1 = town[i]
    x2, _, ind2 = town[i+1]
    cost = abs(x2 - x1)
    heapq.heappush(road, (cost, ind1, ind2))
town.sort(key = lambda x:x[1]) #y座標でソート O(NlogN + N)
for i in range(N-1):
    _, x1, ind1 = town[i]
    _, x2, ind2 = town[i+1]
    cost = abs(x2 - x1)
    heapq.heappush(road, (cost, ind1, ind2))

ans = 0
while road: #O(2N)
    cost, i, j = heapq.heappop(road)
    if isSame(i,j):
        continue
    unite(i, j)
    ans += cost

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
class Union_Find():
    def __init__(self, num):
        self.par = [-1]*(num+1)
        self.siz = [1]*(num+1)

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

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

    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
                self.siz[rx] += self.siz[ry]
            elif self.par[rx] > self.par[ry]:
                self.par[rx] = ry
                self.siz[ry] += self.siz[rx]
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
                self.siz[rx] += self.siz[ry]
        return

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

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

road = []
city.sort()
for i in range(n-1):
    road.append((city[i+1][0] - city[i][0], city[i][2], city[i+1][2]))

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

road.sort()

ans = 0
tree = Union_Find(n)
for i in range(len(road)):
    cost, a, b = road[i]
    if tree.same_checker(a, b):
        continue
    else:
        tree.union(a, b)
        ans += cost

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
 
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self._root(self.table[x])
            return self.table[x]
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
    
    def __str__(self):
        rt=[i if j<0 else j for i,j in enumerate(self.table)]
        return str(rt)

n=I()
p=[]
for i in range(n):
    x,y=LI()
    p.append((x,y,i))
    
X=sorted(p,key=lambda x:x[0])
Y=sorted(p,key=lambda x:x[1])

g=[[] for i in range(n)]
q=[]
for i in range(n-1):
    x0,y0,a=X[i]
    x1,y1,b=X[i+1]
    q.append((abs(x1-x0),a,b))
    
for i in range(n-1):
    x0,y0,a=Y[i]
    x1,y1,b=Y[i+1]
    q.append((abs(y1-y0),a,b))
    
uf=UnionFind(n)
q.sort(reverse=True,key=lambda x:x[0])

ans=0
e=n-1
while e:
    d,a,b=q.pop()
    if uf._root(a)!=uf._root(b):
        ans+=d
        uf.union(a,b)
        e-=1

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
 
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self._root(self.table[x])
            return self.table[x]
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
    
    def __str__(self):
        rt=[i if j<0 else j for i,j in enumerate(self.table)]
        return str(rt)
        
def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    
    # calc
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev

n=I()
p=[]
for i in range(n):
    x,y=LI()
    p.append((x,y,i))
    
X=sorted(p,key=lambda x:x[0])
Y=sorted(p,key=lambda x:x[1])

g=[[] for i in range(n)]
q=[]
for i in range(n-1):
    x0,y0,a=X[i]
    x1,y1,b=X[i+1]
    q.append((min(abs(x1-x0),abs(y1-y0)),a,b))
    
for i in range(n-1):
    x0,y0,a=Y[i]
    x1,y1,b=Y[i+1]
    q.append((min(abs(x1-x0),abs(y1-y0)),a,b))
    
uf=UnionFind(n)
q.sort(reverse=True,key=lambda x:x[0])

ans=0
e=n-1
while e:
    d,a,b=q.pop()
    if uf._root(a)!=uf._root(b):
        ans+=d
        uf.union(a,b)
        e-=1

print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

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

# x,yが小さい順に並び替える
tx = sorted(towns, key=lambda x: x[1])
ty = sorted(towns, key=lambda x: x[2])

# 辺を作ってheapqに突っ込む
q = []
for i in range(1,N):
    heapq.heappush(q, (tx[i][1]-tx[i-1][1], tx[i][0], tx[i-1][0]))
    heapq.heappush(q, (ty[i][2]-ty[i-1][2], ty[i][0], ty[i-1][0]))

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

uf = UnionFind(N)
ans = 0
while q:
    cost, a, b = heapq.heappop(q)
    if not uf.is_same(a,b):
        uf.unite(a,b)
        ans += cost

print(ans)

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix
input = sys.stdin.readline
n = int(input())
xy = [list(map(int,input().split()))+[i] for i in range(n)]
evv = set()
for Key in range(2):
  xy_s = sorted(xy,key = lambda x:x[Key])
  for i in range(1,n):
    evv.add((xy_s[i][2],xy_s[i-1][2],min(abs(xy_s[i-1][0]-xy_s[i][0]),abs(xy_s[i-1][1]-xy_s[i][1]))))
v1,v2,edge = zip(*evv)
csr = csr_matrix((edge,(v1,v2)),shape = (n,n))
mst = minimum_spanning_tree(csr)
print(int(mst.sum()))