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):
class UnionFind(object):
  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ in range(n)]
    self.size = [1 for _ in range(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 union(self, x, y):
    x = self.find(x)
    y = self.find(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.par[y] = x
      self.size[x] += self.size[y]
  def is_same(self, x, y):
    return self.find(x) == self.find(y)
  def get_size(self, x):
    x = self.find(x)
    return self.size[x]

import sys
input = sys.stdin.readline

from heapq import heapify, heappop, heappush

N = int(input())
X = []; Y = []
for i in range(N):
  x,y = map(int,input().split())
  X.append((x,i));Y.append((y,i))
X.sort();Y.sort()
dx = [];dy =[]
for i in range(N-1):
  tx = X[i+1][0]-X[i][0]
  dx.append((tx,(X[i+1][1],X[i][1])))
  ty = Y[i+1][0]-Y[i][0]
  dy.append((ty,(Y[i+1][1],Y[i][1])))
heapify(dx);heapify(dy)

visited = set([])
ans = 0
uf = UnionFind(N)
while uf.get_size(0) < N:
  if not dy or dx[0] <= dy[0]:
    cost, loc = heappop(dx)
  else:
    cost, loc = heappop(dy)
  if uf.is_same(loc[0],loc[1]): 
    continue
  ans += cost
  
  uf.union(loc[0],loc[1])
print(ans)

Solution (Python):
def kruskal():
    '''
    最小全域木のコストを求める
    '''
    cost = 0
    edge.sort()

    for c, u, v in edge:
        if same(u, v):
            continue
        union(u, v)
        cost += c

    return cost


def find(x):
    '''
    xの根を求める
    '''
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def union(x, y):
    '''
    xとyの属する集合を併合する
    '''
    x = find(x)
    y = find(y)
    
    if x == y:
        return False

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

    par[x] += par[y]
    par[y] = x
    return True


def same(x, y):
    '''
    xとyが同じ集合に属するかを判定する
    '''
    return find(x) == find(y)


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

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

par = [-1] * n
print(kruskal())

Solution (Python):
def kruskal():
    '''
    最小全域木のコストを求める
    '''
    cost = 0
    edge.sort()

    for c, u, v in edge:
        if same(u, v):
            continue
        union(u, v)
        cost += c

    return cost


def find(x):
    '''
    xの根を求める
    '''
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def union(x, y):
    '''
    xとyの属する集合を併合する
    '''
    x = find(x)
    y = find(y)
    
    if x == y:
        return False

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

    par[x] += par[y]
    par[y] = x
    return True


def same(x, y):
    '''
    xとyが同じ集合に属するかを判定する
    '''
    return find(x) == find(y)


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

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

par = [-1] * n
print(kruskal())

Solution (Python):
import sys
from collections import defaultdict
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()


def main():
    """
    （考察を述べてなかったので再提出）
    道を全部張った後に最小全域木を求めれば良いー＞プリム
    ただしそのまま実装すると辺の数が|E|=N^2になり、かつ
    プリムの計算量はO(|E|log|E|)なのでTLEする。

    そこで必要になりそうな辺のみに間引くことを考える。
    可能性のある辺はx座標またはy座標が隣り合うものなので、
    そのような辺のみを格納する。
    """
    N = int(input())
    city_x = defaultdict(list)
    city_y = defaultdict(list)
    indexes_x = set()
    indexes_y = set()
    for v in range(N):
        x, y = map(int, input().split())
        city_x[x].append(v)
        city_y[y].append(v)
        indexes_x.add(x)
        indexes_y.add(y)
    indexes_x = list(indexes_x)
    indexes_y = list(indexes_y)
    indexes_x.sort()
    indexes_y.sort()

    
    repn = [[] for _ in range(N)]
    pre_x = -1
    for x in indexes_x:
        pre_v = city_x[x][0]
        for i, v in enumerate(city_x[x]):
            if i == 0: continue
            repn[v].append((0, pre_v))
            repn[pre_v].append((0, v))
            pre_v = v
        if pre_x != -1:
            repn[city_x[pre_x][0]].append((x - pre_x, pre_v))
            repn[pre_v].append((x - pre_x, city_x[pre_x][0]))
        pre_x = x
    pre_y = -1
    for y in indexes_y:
        pre_v = city_y[y][0]
        for i, v in enumerate(city_y[y]):
            if i == 0: continue
            repn[v].append((0, pre_v))
            repn[pre_v].append((0, v))
            pre_v = v
        if pre_y != -1:
            repn[city_y[pre_y][0]].append((y - pre_y, pre_v))
            repn[pre_v].append((y - pre_y, city_y[pre_y][0]))
        pre_y = y
    

    
    unvisited = set([i for i in range(1, N)])
    ans = 0
    q = []
    for cost, v in repn[0]: heappush(q, (cost, v))
    while q:
        cost, v = heappop(q)
        if v not in unvisited: continue
        ans += cost
        unvisited.remove(v)
        if not unvisited: break
        for next_cost, u in repn[v]:
            if u not in unvisited: continue
            heappush(q, (next_cost, u))
    print(ans)





if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import defaultdict
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()


def main():
    """
    道を全部張った後に最小全域木を求めれば良いー＞プリム
    """
    N = int(input())
    city_x = defaultdict(list)
    city_y = defaultdict(list)
    indexes_x = set()
    indexes_y = set()
    for v in range(N):
        x, y = map(int, input().split())
        city_x[x].append(v)
        city_y[y].append(v)
        indexes_x.add(x)
        indexes_y.add(y)
    indexes_x = list(indexes_x)
    indexes_y = list(indexes_y)
    indexes_x.sort()
    indexes_y.sort()

    
    repn = [[] for _ in range(N)]
    pre_x = -1
    for x in indexes_x:
        pre_v = city_x[x][0]
        for i, v in enumerate(city_x[x]):
            if i == 0: continue
            repn[v].append((0, pre_v))
            repn[pre_v].append((0, v))
            pre_v = v
        if pre_x != -1:
            repn[city_x[pre_x][0]].append((x - pre_x, pre_v))
            repn[pre_v].append((x - pre_x, city_x[pre_x][0]))
        pre_x = x
    pre_y = -1
    for y in indexes_y:
        pre_v = city_y[y][0]
        for i, v in enumerate(city_y[y]):
            if i == 0: continue
            repn[v].append((0, pre_v))
            repn[pre_v].append((0, v))
            pre_v = v
        if pre_y != -1:
            repn[city_y[pre_y][0]].append((y - pre_y, pre_v))
            repn[pre_v].append((y - pre_y, city_y[pre_y][0]))
        pre_y = y
    

    
    unvisited = set([i for i in range(1, N)])
    ans = 0
    q = []
    for cost, v in repn[0]: heappush(q, (cost, v))
    while q:
        cost, v = heappop(q)
        if v not in unvisited: continue
        ans += cost
        unvisited.remove(v)
        if not unvisited: break
        for next_cost, u in repn[v]:
            if u not in unvisited: continue
            heappush(q, (next_cost, u))
    print(ans)





if __name__ == "__main__":
    main()

Solution (Python):
from operator import itemgetter

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 {root: self.members(root) for root in self.roots()}



def kruskal(n, edges):  
    uf = UnionFind(n)
    ret = 0
    for u, v, w in edges:
        if not uf.same(u, v):
            ret += w
            uf.union(u, v)
    return ret



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

edges = []
XY.sort(key=itemgetter(1))
for (u, x1, _), (v, x2, _) in zip(XY, XY[1:]):
    edges.append((u, v, abs(x2 - x1)))

XY.sort(key=itemgetter(2))
for (u, _, y1), (v, _, y2) in zip(XY, XY[1:]):
    edges.append((u, v, abs(y2 - y1)))

edges.sort(key=itemgetter(2))
ans = kruskal(n, edges)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from heapq import heappop, heappush,heapify

icase=0
if icase==0:
    n=int(input())
    xy=[[0]*2 for i in range(n)]
    x=[0]*n
    y=[0]*n
    for i in range(n):

        x[i],y[i]=map(int,input().split())
elif icase==1:    
    n=3

    x=[1, 3, 7]
    y=[5, 9, 8]
elif icase==2:    
    n=6

    x=[8, 4, 12,18,13,7]
    y=[3, 9, 19, 1, 5, 6]

xi=[[0]*2 for i in range(n)]
yi=[[0]*2 for i in range(n)]
for i in range(n):
    xi[i]=[x[i],i]
    yi[i]=[y[i],i]
    
xi.sort()
x=xi
y=yi.sort()
y=yi

pair_lst = [i for i in range(n)]
que=[]
for i in range(n-1):
    wi=x[i+1][0]-x[i][0]
    heappush(que,(wi,x[i][1],x[i+1][1]))
    wi=y[i+1][0]-y[i][0]
    heappush(que,(wi,y[i][1],y[i+1][1]))

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

icnt=0
length_sum = 0
while que:
    w, s, t = heappop(que)

    root_s = find(s)
    root_t = find(t)
    if root_s != root_t:
        pair_lst[root_s] = root_t
        length_sum += w
        icnt+=1


print(length_sum)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from heapq import heappop, heappush,heapify

icase=0
if icase==0:
    n=int(input())
    xy=[[0]*2 for i in range(n)]
    x=[0]*n
    y=[0]*n
    for i in range(n):

        x[i],y[i]=map(int,input().split())
elif icase==1:    
    n=3

    x=[1, 3, 7]
    y=[5, 9, 8]
elif icase==2:    
    n=6

    x=[8, 4, 12,18,13,7]
    y=[3, 9, 19, 1, 5, 6]

xi=[[0]*2 for i in range(n)]
yi=[[0]*2 for i in range(n)]
for i in range(n):
    xi[i]=[x[i],i]
    yi[i]=[y[i],i]
    
xi.sort()
x=xi
y=yi.sort()
y=yi

pair_lst = [i for i in range(n)]
que=[]
for i in range(n-1):
    wi=x[i+1][0]-x[i][0]
    heappush(que,(wi,x[i][1],x[i+1][1]))
    wi=y[i+1][0]-y[i][0]
    heappush(que,(wi,y[i][1],y[i+1][1]))

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

icnt=0
length_sum = 0
while que:
    w, s, t = heappop(que)

    root_s = find(s)
    root_t = find(t)
    if root_s != root_t:
        pair_lst[root_s] = root_t
        length_sum += w
        icnt+=1


print(length_sum)

Solution (Python):
from copy import deepcopy as copy
from operator import itemgetter

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

    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):
        x = self.find(x)
        y = self.find(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 same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.par[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if root == self.find(i)]        

def main():
    n = int(input())
    bridge = [None]*n
    for i in range(n):
        bridge[i] = [int(x) for x in input().split()]+[i]

    judge = []

    bridge.sort()
    for i in range(n-1):
        judge.append((bridge[i+1][0]-bridge[i][0], bridge[i][2], bridge[i+1][2]))

    bridge.sort(key=itemgetter(1))
    for i in range(n-1):
        judge.append((bridge[i+1][1]-bridge[i][1], bridge[i][2], bridge[i+1][2]))
    
    judge.sort()
    union = UnionFind(n)
    count = 0
    cost = 0
    for k in range(2*n):
        c, i, j = judge[k]
        if union.same(i, j):
            continue
        union.union(i, j)
        cost += c
        count += 1
        if count == n-1:
            break
    
    print(cost)

if __name__ == "__main__":
    main()

Solution (Python):
class UnionFindTree():

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

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

    def unite(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

    def count_node(self,x):
        return -1 * self.root[self.find_root(x)]
from heapq import heapify, heappop

n = int(input())

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

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

diff = []

for i in range(n-1):
    diff.append((sort_x[i+1][1]-sort_x[i][1],sort_x[i][0],sort_x[i+1][0]))
    diff.append((sort_y[i+1][2]-sort_y[i][2],sort_y[i][0],sort_y[i+1][0]))


heapify(diff)

uft = UnionFindTree(n)

ans = 0
while diff:
    w, s, t = heappop(diff)
    if not uft.is_same(s,t):
        uft.unite(s,t)
        ans += w

print(ans)

Solution (Python):
from heapq import heapify, heappop, heappush
N, *A = map(int, open(0).read().split())
*A, = zip(*[iter(A)]*2)
A = [(x, y, i) for i, (x, y) in enumerate(A)]
A.sort()
G = []
x0, y0, i0 = A[0]
for x, y, i in A[1:]:
    c = min(abs(x-x0), abs(y-y0))
    heappush(G, (c, i0, i))
    x0, y0, i0 = x, y, i
A.sort(key=lambda x: x[1])
x0, y0, i0 = A[0]
for x, y, i in A[1:]:
    c = min(abs(x-x0), abs(y-y0))
    heappush(G, (c, i0, i))
    x0, y0, i0 = x, y, i


class UnionFind:
    def __init__(self, n=0):
        self.d = [-1]*n
        self.u = n

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if x > y:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        self.u -= 1
        return True

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

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

    def num_union(self):
        return self.u


ans = 0
u = UnionFind(N)
while u.num_union() > 1:
    c, a, b = heappop(G)
    if u.same(a, b):
        continue
    u.unite(a, b)
    ans += c

print(ans)

Solution (Python):
import sys
import pprint
sys.path.append('C:\\ARIHON')



import array
import collections
from operator import itemgetter

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
 
Edge = collections.namedtuple("Edge", "start end weight")

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

    lxsort = sorted(l,key=itemgetter(0))
    for i in range(n-1):
        edges.append(Edge(lxsort[i][2],lxsort[i+1][2],lxsort[i+1][0]-lxsort[i][0]))
    
    lysort = sorted(l,key=itemgetter(1))
    for i in range(n-1):
        edges.append(Edge(lysort[i][2],lysort[i+1][2],lysort[i+1][1]-lysort[i][1]))
    
    mst = compute_mst_kruskal(n,edges)

    print(sum(edge.weight for edge in mst))
 
if __name__ == '__main__':
    main()

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


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())
xy = [list(map(int, input().split()))+[i] for i in range(n)]
G = []

xy.sort()
for j in range(1, n):
    sx, sy, si = xy[j-1]
    tx, ty, ti = xy[j]
    G.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]
    G.append((min(abs(sx-tx), abs(sy-ty)), si, ti))

uf = UnionFind(n)
ans = 0
G.sort()
for c, x, y in G:
    if uf.same(x, y):
        continue
    uf.union(x, y)
    ans += c
print(ans)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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 main():
    N = int(readline())
    X = []
    Y = []

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

    X.sort()
    Y.sort()
    L = []
    for i in range(N - 1):
        L.append([X[i][1], X[i + 1][1], X[i + 1][0] - X[i][0]])
        L.append([Y[i][1], Y[i + 1][1], Y[i + 1][0] - Y[i][0]])
    L.sort(key=lambda x: x[2])

    uf = UnionFind(N)
    ans = 0
    for s, t, w in L:
        if not uf.same(s, t):
            uf.union(s, t)
            ans += w
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


from heapq import heappush, heappop

class UnionFind(object):
    def __init__(self, n):
        self.n = 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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return False
        else:
            if self.par[x] > self.par[y]:
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x
            return True

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

    def size(self, x):
        return -self.par[self.find(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.par) if x < 0]

    def group_count(self):
        return len(self.roots())

N = int(input())
X, Y = [], []
Loc = []
for n in range(N):
    xi, yi = map(int, input().split())
    X.append((xi, n))
    Y.append((yi, n))
    Loc.append((n, xi, yi))





























edges = []
X.sort()
Y.sort()
for i in range(N - 1):
    wxi = abs(X[i][0] - X[i + 1][0])
    wyi = abs(Y[i][0] - Y[i + 1][0])
    heappush(edges, (wxi, X[i][1], X[i + 1][1]))
    heappush(edges, (wyi, Y[i][1], Y[i + 1][1]))


uf = UnionFind(N)
cost = 0
while len(edges) > 0:
    (w, u, v) = heappop(edges)
    if uf.unite(u, v):
        cost += w
print(cost)