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

Solution (Python):
import array
import collections


Edge = collections.namedtuple("Edge", "start end weight")


class UnionFind(object):

    def __init__(self, number_of_nodes):  
        self.par = array.array("L", range(number_of_nodes))
        self.rank = array.array("L", (0 for i in range(number_of_nodes)))

    def root(self, node):  
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r  
            return r

    def in_the_same_set(self, node1, node2):  
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):  
        x = self.root(node1)
        y = self.root(node2)
        if x == y:
            pass
        elif self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1



def compute_mst_kruskal(max_v, edges):
    edges.sort(key=lambda edge: edge.weight)
    uf = UnionFind(max_v)
    mst = []
    for edge in edges:
        if not uf.in_the_same_set(edge.start, edge.end):
            uf.unite(edge.start, edge.end)
            mst.append(edge)
    return mst


def main():
    n = int(input())
    XY = [list(map(int, input().split())) + [i] for i in range(n)]
    XY.sort()
    edges = []
    for (x1, y1, i1), (x2, y2, i2) in zip(XY, XY[1:]):
        edges.append(Edge(i1, i2, min(abs(x1 - x2), abs(y1 - y2))))
    XY.sort(key=lambda x:x[1] )
    for (x1, y1, i1), (x2, y2, i2) in zip(XY, XY[1:]):
        edges.append(Edge(i1, i2, min(abs(x1 - x2), abs(y1 - y2))))
    
    mst = compute_mst_kruskal(n, edges)
    print(sum(edge.weight for edge in mst))


if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappop, heappush


class UnionFind(object):

    def __init__(self, N):
        self.tree = [i for i in range(N)]
        self.rank = [0] * (N + 1)
        self.size = [1] * N  

    def find(self, x):
        if self.tree[x] == x:
            return x
        else:
            self.tree[x] = self.find(self.tree[x])  
            return self.tree[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.tree[x] = y
            self.size[y] += self.size[x]
        else:
            self.tree[y] = x
            self.size[x] += self.size[y]

        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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


def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))


N = I()
X = [None] * N
Y = [None] * N
for i in range(N):
    x, y = MI()
    X[i] = (x, i, x, y)
    Y[i] = (y, i, x, y)
X.sort()
Y.sort()


q = list()
for i in range(N - 1):
    for axis in [X, Y]:
        _, t0, x0, y0 = axis[i]
        _, t1, x1, y1 = axis[i + 1]
        cost = min(abs(x1 - x0), abs(y1 - y0))
        heappush(q, (cost, t0, t1))

uf = UnionFind(N)
ans = 0
while len(q) > 0:
    cost, t0, t1 = heappop(q)
    if not uf.has_same_parent(t0, t1):
        uf.unite(t0, t1)
        ans += cost
print(ans)

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

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

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

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

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

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

Solution (Python):

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)

Solution (Python):






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

Solution (Python):






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

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











N = int(input())


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)

Solution (Python):
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

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


from itertools import combinations


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:  
            return i
        else:
            self.parent[i] = self.findRoot(self.parent[i])  
            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():
    
    N = [int(x) for x in sys.stdin.readline().split()][0]  
    
    

    
    
    grid = [[int(x) for x in sys.stdin.readline().split()] + [i]
            for i in range(N)]  

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

    edge_list = []
    
    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))

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





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)

Solution (Python):


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)


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

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

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

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

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

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() 
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]) 
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: 
    cost, i, j = heapq.heappop(road)
    if isSame(i,j):
        continue
    unite(i, j)
    ans += cost

print(ans)

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

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