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):
    '''Represents a data structure that tracks a set of elements partitioned
       into a number of disjoint (non-overlapping) subsets.
    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.
    See:
    https://www.youtube.com/watch?v=zV3Ul2pA2Fw
    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
    https://atcoder.jp/contests/abc120/submissions/4444942
    '''

    def __init__(self, number_count: int):
        '''
        Args:
            number_count: The size of elements (greater than 2).
        '''
        self.parent_numbers = [-1 for _ in range(number_count)]

    def find_root(self, number: int) -> int:
        '''Follows the chain of parent pointers from number up the tree until
           it reaches a root element, whose parent is itself.
        Args:
            number: The trees id (0-index).
        Returns:
            The index of a root element.
        '''
        if self.parent_numbers[number] < 0:
            return number

        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])
        return self.parent_numbers[number]

    def get_group_size(self, number: int) -> int:
        '''
        Args:
            number: The trees id (0-index).
        Returns:
            The size of group.
        '''
        return -self.parent_numbers[self.find_root(number)]

    def is_same_group(self, number_x: int, number_y: int) -> bool:
        '''Represents the roots of tree number_x and number_y are in the same
           group.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        return self.find_root(number_x) == self.find_root(number_y)

    def merge_if_needs(self, number_x: int, number_y: int) -> bool:
        '''Uses find_root to determine the roots of the tree number_x and
           number_y belong to. If the roots are distinct, the trees are combined
           by attaching the roots of one to the root of the other.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        x = self.find_root(number_x)
        y = self.find_root(number_y)

        if x == y:
            return False

        if self.get_group_size(x) >= self.get_group_size(y):
            self.parent_numbers[x] += self.parent_numbers[y]
            self.parent_numbers[y] = x
        else:
            self.parent_numbers[y] += self.parent_numbers[x]
            self.parent_numbers[x] = y
        return True


def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    x = [None for _ in range(n)]
    y = [None for _ in range(n)]

    for i in range(n):
        xi, yi = map(int, input().split())
        xi -= 1
        yi -= 1

        x[i] = (xi, i)
        y[i] = (yi, i)

    new_x = sorted(x)
    new_y = sorted(y)
    road = list()

    for _from, _to in zip(new_x, new_x[1:]):
        cost = abs(_from[0] - _to[0])
        road.append((_from[1], _to[1], cost))

    for _from, _to in zip(new_y, new_y[1:]):
        cost = abs(_from[0] - _to[0])
        road.append((_from[1], _to[1], cost))

    new_road = sorted(road, key=lambda x: x[2])
    uf = UnionFind(n)
    ans = 0

    for nr in new_road:
        if uf.merge_if_needs(nr[0], nr[1]):
            ans += nr[2]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def solve_abc065d():
    from collections import namedtuple
    from operator import attrgetter
    from itertools import tee
    import sys

    input = sys.stdin.readline

    City = namedtuple('City', 'x y idx')
    Edge = namedtuple('Edge', 'cost a b')
    N = int(input())

    cities = []
    for city_idx in range(N):
        x, y = map(int, input().split())
        c_ = City(x, y, city_idx)
        cities.append(c_)
    cities_x_asc = sorted(cities, key=attrgetter('x'))
    cities_y_asc = sorted(cities, key=attrgetter('y'))

    edges = []

    it_x = iter(cities_x_asc)
    gx1, gx2 = tee(it_x, 2)
    next(gx2)
    for c1, c2 in zip(gx1, gx2):
        d_ = c2.x - c1.x
        e_ = Edge(d_, c1.idx, c2.idx)
        edges.append(e_)
    

    it_y = iter(cities_y_asc)
    gy1, gy2 = tee(it_y, 2)
    next(gy2)
    for c1, c2 in zip(gy1, gy2):
        d_ = c2.y - c1.y
        e_ = Edge(d_, c1.idx, c2.idx)
        edges.append(e_)
    

    edges.sort(key=attrgetter('cost'))

    
    
    
    

    
    *p, = range(N)

    def root(x):
        if x == p[x]:
            return x
        p[x] = y = root(p[x])
        return y

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

    mi = 0
    for e_ in edges:
        if unite(e_.a, e_.b):
            mi += e_.cost

    

    print(mi)
    return


if __name__ == '__main__':
    solve_abc065d()

Solution (Python):
class UnionFind:
    def __init__(self, n):
        
        self.par = [i for i in range(n+1)]
        
        self.rank = [0] * (n+1)
        
        self.count = [1] * (n+1)

    
    def find(self, x):
        
        root = x
        queue = [x]
        data = []
        while queue:
            now = queue.pop()
            if self.par[now] == now:
                root = now
            else:
                
                data.append(now)
                queue.append(self.par[now])
        
        for y in data:
            self.par[y] = root
        return root

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        t = (x == y)
        if UnionFind.same_check(self, x, y):
            return t
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        return t

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

    
    def size(self, x):
        q = UnionFind.find(self, x)
        return self.count[q]


n = int(input())
vertex = []
for i in range(n):
    xi,yi = map(int,input().split())
    vertex.append((xi, yi, i))

edge = []
vertex.sort()
for i in range(1, n):
    edge.append((vertex[i][0] - vertex[i - 1][0], vertex[i][2], vertex[i - 1][2]))

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

edge.sort()
u = UnionFind(n)
ans = 0
for d, i, j in edge:
    if u.union(i, j):
        continue
    ans += d

print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        
        self.par = [i for i in range(n+1)]
        
        self.rank = [0] * (n+1)
        
        self.count = [1] * (n+1)

    
    def find(self, x):
        
        root = x
        queue = [x]
        data = []
        while queue:
            now = queue.pop()
            if self.par[now] == now:
                root = now
            else:
                
                data.append(now)
                queue.append(self.par[now])
        
        for y in data:
            self.par[y] = root
        return root

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        t = (x == y)
        if UnionFind.same_check(self, x, y):
            return t
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        return t

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

    
    def size(self, x):
        q = UnionFind.find(self, x)
        return self.count[q]


n = int(input())
vertex = []
for i in range(n):
    xi,yi = map(int,input().split())
    vertex.append((xi, yi, i))

edge = []
vertex.sort()
for i in range(1, n):
    edge.append((vertex[i][0] - vertex[i - 1][0], vertex[i][2], vertex[i - 1][2]))

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

edge.sort()
u = UnionFind(n)
ans = 0
for d, i, j in edge:
    if u.union(i, j):
        continue
    ans += d

print(ans)

Solution (Python):
class UnionFind:
  def __init__(self, n):
    self.parents = list(range(n))
    self.ranks = [0] * n

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

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

  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    if x == y:
      return
    if self.ranks[x] < self.ranks[y]:
      self.parents[x] = y
    else:
      self.parents[y] = x
      if self.ranks[x] == self.ranks[y]:
        self.ranks[x] += 1

n = int(input())
X = [None] * n
Y = [None] * n
for i in range(n):
  x, y = map(int, input().split())
  X[i] = (x, i)
  Y[i] = (y, i)
X.sort(key=lambda x: x[0])
Y.sort(key=lambda y: y[0])
Z = [None] * (2 * n - 2)
for i in range(n - 1):
  Z[2 * i] = (X[i + 1][0] - X[i][0], X[i][1], X[i + 1][1])
  Z[2 * i + 1] = (Y[i + 1][0] - Y[i][0], Y[i][1], Y[i + 1][1])
Z.sort(key=lambda z: z[0])

u = UnionFind(n)
total = 0
count = 0
for z in Z:
  d, a, b = z
  if not u.same(a, b):
    u.unite(a, b)
    total += d
    count += 1
    if count == n - 1:
      break
print(total)

Solution (Python):
import heapq

def prim():
    used = [1] * n
    used[0] = 0
    lis = []
    res = 0
    
    for a,b in edge[0]:
        heapq.heappush(lis,a*(10**6)+b)
        
    while lis:
        minedge = heapq.heappop(lis)
        
        if used[minedge%(10**6)] == 0:
            continue

        v = minedge%(10**6)
        used[v] = 0

        for q in edge[v]:
            if used[q[1]] == 1:
                heapq.heappush(lis , q[0]*(10**6) + q[1] )
        res += (minedge // (10**6))
    return res

n = int(input())
edge = [[] for _ in range(n)]
xsort = [[0]*2 for _ in range(n)]
ysort = [[0]*2 for _ in range(n)]

for i in range(n):
    x ,y = map(int,input().split())
    xsort[i][0] = x
    ysort[i][0] = y
    xsort[i][1] = i
    ysort[i][1] = i
xsort.sort()
ysort.sort()

for i in range(n-1):
    edge[xsort[i][1]].append([xsort[i+1][0] - xsort[i][0] , xsort[i+1][1]])
    edge[xsort[i+1][1]].append([xsort[i+1][0] - xsort[i][0] , xsort[i][1]])
    edge[ysort[i][1]].append([ysort[i+1][0] - ysort[i][0] , ysort[i+1][1]])
    edge[ysort[i+1][1]].append([ysort[i+1][0] - ysort[i][0] , ysort[i][1]])
    
print(prim())

Solution (Python):
import sys 
input = sys.stdin.readline
n = int(input())
data = []
class UnionFind:
    def __init__(self, n):
        
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)
    def find(self, x):
        
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self, x, y):
        
        return self.find(x) == self.find(y)
    def union(self, x, y):
        
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
        else:
            self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
    def getsize(self, x):
        p = self.find(x)
        return self.size[p]
x = []
y = []
for i in range(n):
    a,b = map(int, input().split())
    x.append([a,i+1])
    y.append([b,i+1])
x.sort(key = lambda x: x[0])
y.sort(key = lambda x: x[0])
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]])

edge.sort(key = lambda x: x[0])
UF = UnionFind(n)
ans = 0
for i in range(len(edge)):
    cost,a,b = edge[i]
    if UF.same_check(a,b):
        continue
    else:
        ans += cost
        UF.union(a,b)
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
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()
edges=[]
for i in range(n-1):
  edges.append((abs(x[i][0]-x[i+1][0]),x[i][1],x[i+1][1]))
  edges.append((abs(y[i][0]-y[i+1][0]),y[i][1],y[i+1][1]))
edges.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 kruskal(n, edges):
    uf = UnionFind(n)
    res = 0
    for e in edges:
        w, s, t = e
        if not uf.same(s, t):
            res+=w
            uf.union(s, t)
    return res
print(kruskal(n, edges))

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import heapq
class Prim():
    """
    ・無向辺
    ・負のコストがあっても大丈夫？
    ・計算量はO(E log|V|)　
    ・heapを使う
    """
    
    class Edge():
        
        
        def __init__(self, _to, _cost):
            self.to =_to
            self.cost = _cost
    
    def __init__(self, V):
        
        self.G = [[] for _ in range(V)] 
        self. _E = 0 
        self._V = V 
    
    
    def E(self):
        return self._E
    
    
    def V(self):
        return self._V
    
    def add(self, _from, _to, _cost):
        
        self.G[_from].append(self.Edge(_to,_cost))
        self._E +=1
        
    def add2(self, _from, _to, _cost):
        
        self.G[_from].append(self.Edge(_to, _cost))
        self.G[_to].append(self.Edge(_from, _cost))
        self._E +=1
        
    def CostSum(self):
        
        
        used = [0]*self.V()
        que = [] 
        heapq.heappush(que,(0,0)) 
        ans =0 
        
        while len(que)!=0:
            
            
            cost,v = heapq.heappop(que)
            
            
            if used[v] ==1:
                continue
            used[v] = 1
            ans += cost
            
            
            for i in range(len(self.G[v])):
                e = self.G[v][i] 
                
                if used[e.to]==0:
                    heapq.heappush(que,(e.cost,e.to))
                    
        return ans   



def main():
    mod=10**9+7
    N=I()
    xyi=[[0,0,0] for _ in range(N)]
    for i in range(N):
        xyi[i][0],xyi[i][1]=MI()
        xyi[i][2]=i
    xyi.sort()
    prim = Prim(N)
    for i in range(N-1):
        prim.add2(xyi[i][2],xyi[i+1][2],abs(xyi[i][0]-xyi[i+1][0]))
        
    xyi.sort(key=lambda x: x[1])
    for i in range(N-1):
        prim.add2(xyi[i][2],xyi[i+1][2],abs(xyi[i][1]-xyi[i+1][1]))

        
    ans = prim.CostSum()
    
    print(ans)
    

main()

Solution (Python):
import sys
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
import decimal
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N = INT()
    x = []
    y = []
    for _ in range(N):
        xx,yy = MAP()
        x.append(xx)
        y.append(yy)
    x = [(x[i],i) for i in range(N)]
    y = [(y[i],i) for i in range(N)]
    x.sort(key=lambda x:x[0])
    y.sort(key=lambda x:x[0])
    edges = []
    for i in range(N-1):
        edges.append((x[i][1],x[i+1][1],x[i+1][0]-x[i][0]))
        edges.append((y[i][1],y[i+1][1],y[i+1][0]-y[i][0]))
    edges.sort(key=lambda x:x[2])
    uf = UnionFind(N)
    answer = 0
    for i in range(len(edges)):
        s,t,w = edges[i]
        if not uf.same(s,t):
            uf.union(s,t)
            answer += w
    print(answer)
    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
import decimal
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N = INT()
    x = []
    y = []
    for _ in range(N):
        xx,yy = MAP()
        x.append(xx)
        y.append(yy)
    x = [(x[i],i) for i in range(N)]
    y = [(y[i],i) for i in range(N)]
    x.sort()
    y.sort()
    edges = []
    for i in range(N-1):
        edges.append((x[i][1],x[i+1][1],x[i+1][0]-x[i][0]))
        edges.append((y[i][1],y[i+1][1],y[i+1][0]-y[i][0]))
    edges.sort(key=lambda x:x[2])
    uf = UnionFind(N)
    answer = 0
    for i in range(len(edges)):
        s,t,w = edges[i]
        if not uf.same(s,t):
            uf.union(s,t)
            answer += w
    print(answer)
    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from heapq import heappush, heappop, heapify
from pprint import pprint

N = int(sys.stdin.readline().strip())

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

x_sorted = sorted(points, key=lambda x:x[1])
y_sorted = sorted(points, key=lambda x:x[2])


edges = [[] for _ in range(N)]
for i, (p1, x1, y1) in enumerate(x_sorted[:-1]):
    p2, x2, y2 = x_sorted[i+1]
    edges[p1].append((p2, x2 - x1))
    edges[p2].append((p1, x2 - x1))

for i, (p1, x1, y1) in enumerate(y_sorted[:-1]):
    p2, x2, y2 = y_sorted[i+1]
    edges[p1].append((p2, y2 - y1))
    edges[p2].append((p1, y2 - y1))


used = set()
q = []
for i in range(N):
    if len(edges[i]):
        for t, w in edges[i]:
            q.append((w, t))
        used.add(i)
        break
heapify(q)

ans = 0
while q:
    w, s = heappop(q)
    if s in used:
        continue
    used.add(s)
    ans += w
    for t, w in edges[s]:
        if t in used:
            continue
        heappush(q, (w, t))

print(ans)

Solution (Python):
from heapq import heappop, heappush, heapify
import sys
input = lambda: sys.stdin.readline().rstrip()

def find(x):
    if parents[x] < 0:
        return x
    else:
        parents[x] = find(parents[x])
        return parents[x]
def union(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return
    if parents[x] > parents[y]:
        x, y = y, x
    parents[x] += parents[y]
    parents[y] = x

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

N = int(input())

verticies_x = []
verticies_y = []

for i in range(N):
    x, y = map(int, input().split())
    verticies_x.append((x,i))
    verticies_y.append((y,i))
verticies_x.sort()    
verticies_y.sort()

edge = []

for i in range(N-1):
    tmp_x = verticies_x[i+1][0] - verticies_x[i][0]
    tmp_y = verticies_y[i+1][0] - verticies_y[i][0]
    edge.append((tmp_x, verticies_x[i][1], verticies_x[i+1][1]))
    edge.append((tmp_y, verticies_y[i][1], verticies_y[i+1][1]))

ans = 0
edge.sort()
parents = [-1] * N
for cost, s, g in edge:
    if same(s,g):
        continue
    else:
        union(s,g)
        ans += cost
print(ans)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()

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

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

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)