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

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


tx = sorted(towns, key=lambda x: x[1])
ty = sorted(towns, key=lambda x: x[2])


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 
        self.count = 0 
    
    
    def root(self, a):
        if self.parent[a] == a:
            return a
        else:
            
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    
    
    def is_same(self, a, b):
        return self.root(a) == self.root(b)
    
    
    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)

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

Solution (Python):


from heapq import heappush, heappop

def prim_heap(edges, n):
    visited = [False] * n
    heap = []
    start = 0
    for e in edges[start]:
        heappush(heap, e)
    visited[start] = True

    res = 0
    while heap:
        cost, v = heappop(heap)
        if visited[v]:
            continue
        visited[v] = True
        res += cost
        for c,u in edges[v]:
            if visited[u]:
                continue
            heappush(heap, (c,u))
    return res

n = int(input())
edges = []

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

x = sorted(range(n), key=lambda i:edges[i][0])
y = sorted(range(n), key=lambda i:edges[i][1])
edge_list = [[] for _ in range(n)]
manhattan = lambda a,b: min(abs(a[0] - b[0]), abs(a[1] - b[1]))
for i in range(n):
    if i + 1 < n:
        edge_list[x[i]].append((manhattan(edges[x[i]], edges[x[i+1]]), x[i+1]))
        edge_list[x[i+1]].append((manhattan(edges[x[i]], edges[x[i+1]]), x[i]))
        edge_list[y[i]].append((manhattan(edges[y[i]], edges[y[i+1]]), y[i+1]))
        edge_list[y[i+1]].append((manhattan(edges[y[i]], edges[y[i+1]]), y[i]))

print(prim_heap(edge_list, n))

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

def main():
    N = int(input())
    rx,ry = [],[]
    _root = []
    for i in range(N):
        a,b = map(int,input().split())
        rx.append((a,i))
        ry.append((b,i))
    
    I = [i for i in range(N)]
    rank = [1 for _ in range(N)]
    def root(x):
        if x == I[x]:
            return x
        I[x] = root(I[x])
        return I[x]
    
    def unite(x,y):
        px,py = root(x),root(y)
        rx,ry = rank[px],rank[py]
        if rx > ry:
            I[py] = px
        else:
            I[px] = py
            if rx == ry:
                rank[py] += 1

    ans = 0
    rx.sort()
    ry.sort()
    for i in range(N-1):
        dx = rx[i+1][0]-rx[i][0]
        dy = ry[i+1][0]-ry[i][0]
        _root.append((dx,rx[i][1],rx[i+1][1]))
        _root.append((dy,ry[i][1],ry[i+1][1]))
        
    _root.sort()
    a = len(_root)
    for i in range(a):
        cost,now,fol = _root[i]
        if (root(now) == root(fol)):
            continue
        ans += cost
        unite(now,fol)
        
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
import heapq
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
p = []
for i in range(N):
  x, y = map(int, input().split())
  p.append((x, y, i))

e = dd(list)
ps = sorted(p, key = lambda x: (x[1], x[0]))
for i in range(N - 1):
  u = ps[i][2]
  v = ps[i + 1][2]
  d = min(abs(p[u][0] - p[v][0]), abs(p[u][1] - p[v][1]))
  e[u].append((v, d))
  e[v].append((u, d))
ps.sort(key = lambda x: (x[0], x[1]))
for i in range(N - 1):
  u = ps[i][2]
  v = ps[i + 1][2]
  d = min(abs(p[u][0] - p[v][0]), abs(p[u][1] - p[v][1]))
  e[u].append((v, d))
  e[v].append((u, d))


class prim:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def MSTcost(self):
    h = []
    visited = [0] * (self.n + 1)
    ks = list(self.e.keys())
    b = pow(10, 10)
    for edge in self.e[ks[0]]:
      heapq.heappush(h, edge[1] * b + edge[0])
    res = 0
    visited[ks[0]] = 1
    while len(h):
      p = heapq.heappop(h)
      p0 = p // b
      p1 = p % b
      if visited[p1]: continue
      visited[p1] = 1
      for q in self.e[p1]:
        if visited[q[0]]:
          continue
        heapq.heappush(h, q[1] * b + q[0])
      res += p0
    return res

pri = prim(N, e)
print(pri.MSTcost())

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

def main():
    N = int(input())
    x,y = [],[]
    root = [[] for _ in range(N)]
    go = [True for _ in range(N)]
    for i in range(N):
        _x,_y = map(int,input().split())
        x.append((_x,i))
        y.append((_y,i))
        
    x.sort()
    y.sort()
    
    for i in range(N-1):
        dx = x[i+1][0] - x[i][0]
        dy = y[i+1][0] - y[i][0]
        root[x[i][1]].append((dx,x[i+1][1]))
        root[x[i+1][1]].append((dx,x[i][1]))
        root[y[i][1]].append((dy,y[i+1][1]))
        root[y[i+1][1]].append((dy,y[i][1]))
    
    ans = 0    
    queue = root[0]
    heapq.heapify(queue)
    go[0] = False
    while queue:
        cost,following = heapq.heappop(queue)
        if not go[following]:
            continue
        go[following] = False
        for e in root[following]:
            if go[e[1]]:
                heapq.heappush(queue,e)
        ans += cost
        
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        
        
        self.par = [i for i in range(n+1)]
        
        self.rank = [0] * (n+1)
        
        self.size = [1] * (n+1)
        
        self.tree = [True] * (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 union(self, x, y):
        """ 併合 """
        
        x = self.find(x)
        y = self.find(y)

        
        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def is_same(self, x, y):
        """ 同じ集合に属するか判定 """
        return self.find(x) == self.find(y)

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            res = set()
            for i in range(self.n+1):
                res.add(self.find(i))
            
            return len(res) - 1
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

N = INT()
X = []
Y = []
for i in range(N):
    x, y = MAP()
    X.append((x, i))
    Y.append((y, i))


X.sort()
Y.sort()
edges = []
for i in range(N-1):
    x1, u = X[i]
    x2, v = X[i+1]
    edges.append((x2-x1, u, v))
    y1, u = Y[i]
    y2, v = Y[i+1]
    edges.append((y2-y1, u, v))


edges.sort()
uf = UnionFind(N)
ans = 0
for c, a, b in edges:
    if not uf.is_same(a, b):
        uf.union(a, b)
        ans += c
print(ans)

Solution (Python):
import heapq


def prim(n, s, edges):
    
    
    used = [False] * n
    edgelist = []
    for e in edges[s]:
        heapq.heappush(edgelist, e)
    used[s] = True
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]:
            continue
        used[minedge[1]] = True
        for e in edges[minedge[1]]:
            if not used[e[1]]:
                heapq.heappush(edgelist, e)
        res += minedge[0]
    return res


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

edges = [[] for _ in range(N)]
sorted_xy = sorted(XY, key=lambda x: x[1])
for i in range(N-1):
    a = sorted_xy[i][0]
    b = sorted_xy[i+1][0]
    cost = sorted_xy[i+1][1] - sorted_xy[i][1]
    edges[a].append((cost, b))
    edges[b].append((cost, a))
sorted_xy = sorted(XY, key=lambda x: x[2])
for i in range(N-1):
    a = sorted_xy[i][0]
    b = sorted_xy[i+1][0]
    cost = sorted_xy[i+1][2] - sorted_xy[i][2]
    edges[a].append((cost, b))
    edges[b].append((cost, a))
ans = prim(N, 0, edges)
print(ans)

Solution (Python):
'''
　 ∧_,,∧    究極奥義「WAがACになーれ！！」
　（`・ω・)つ━☆・*。
　⊂　　 ノ 　　　・゜+.
　 し’´Ｊ　　*・ 
'''
import sys
input = sys.stdin.readline
class UnionFind():
   
   
   def __init__(self, n):
       self.n = n
       
       
       self.root = [-1]*(n+1)
       
       self.rnk = [0]*(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.rnk[x] > self.rnk[y]):
           self.root[x] += self.root[y]
           self.root[y] = x
       else:
           self.root[y] += self.root[x]
           self.root[x] = y
           
           if(self.rnk[x] == self.rnk[y]):
               self.rnk[y] += 1
   
   def isSameGroup(self, x, y):
       return self.Find_Root(x) == self.Find_Root(y)
   
   def Count(self, x):
       return -self.root[self.Find_Root(x)]
n=int(input())
p=[list(map(int,input().split()))+[i] for i in range(n)]
p.sort()
d=[0]*(2*n-2)
for i in range(n-1):
    d[i]=[p[i][2],p[i+1][2],p[i+1][0]-p[i][0]]
p.sort(key=lambda x:x[1])
for i in range(n-1):
    d[i-1+n]=[p[i][2],p[i+1][2],p[i+1][1]-p[i][1]]
d.sort(key=lambda x:x[2])
h = UnionFind(n) 
cost = 0
for i in d:
    if not h.isSameGroup(i[0],i[1]):
        h.Unite(i[0],i[1])
        cost += i[2]
print(cost)

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

xl = sorted(xl)
yl = sorted(yl)

import heapq
al = []
for i in range(n-1):
    al.append((abs(xl[i+1][0] - xl[i][0]), xl[i][1], xl[i+1][1]))
    al.append((abs(yl[i+1][0] - yl[i][0]), yl[i][1], yl[i+1][1]))

heapq.heapify(al)

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

uf = UnionFind(n)

ans = 0
for i in range(n-1):
    while True:
        c, a, b = heapq.heappop(al)
        if not uf.same(a, b):
            ans += c
            uf.union(a,b)
            break

print(ans)

Solution (Python):
class UF:
    def __init__(self, N):
        self.uf = [-1]*N
        self.n = N

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

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

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

import sys
input = sys.stdin.readline

N = int(input())
P = [tuple(map(int, [i]+input().split())) for i in range(N)]

uf = UF(N)

Px = sorted(P, key=lambda p:p[1])
Py = sorted(P, key=lambda p:p[2])

E = []
for i in range(N-1):
    E.append((Px[i+1][1]-Px[i][1], Px[i][0], Px[i+1][0]))
    E.append((Py[i+1][2]-Py[i][2], Py[i][0], Py[i+1][0]))
E = sorted(E)

ans = 0
for c, p1, p2 in E:
    if uf.find(p1)!=uf.find(p2):
        ans += c
        uf.union(p1, p2)

print(ans)

Solution (Python):
n=int(input())
l=[]
for i in range(n):
    l.append([i]+list(map(int,input().split())))
g = []
l.sort(key=lambda x: x[1])
for i in range(n-1):
    g.append([l[i][0],l[i+1][0],abs(l[i][1]-l[i+1][1])])
l.sort(key=lambda x: x[2])
for i in range(n-1):
    g.append([l[i][0],l[i+1][0],abs(l[i][2]-l[i+1][2])])

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 minimum_spanning_tree(g,n):


    g.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    ret = 0
    for sg in g:
        a,b,c = sg[0],sg[1],sg[2]
        if not uf.same(a,b):
            uf.union(a,b)
            ret += c
    return ret

print(minimum_spanning_tree(g,n))

Solution (Python):
N = int(input())
XY = []
for i in range(N):
  x,y = map(int,input().split())
  XY.append((x,y,i))
E = []
XY.sort()
for i in range(N-1):
  E.append((abs(XY[i+1][0] - XY[i][0]),XY[i][2],XY[i+1][2]))
XY = sorted(XY,key=lambda x:x[1])
for i in range(N-1):
  E.append((abs(XY[i+1][1] - XY[i][1]),XY[i][2],XY[i+1][2]))

*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

E.sort()
ans = 0
for c, v, w in E:
    if unite(v, w):
        ans += c
print(ans)

Solution (Python):
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

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

    def root(self, u):
        v = self.state[u]
        if v < 0: return u
        self.state[u] = res = self.root(v)
        return res

    def merge(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if ru == rv: return
        du = self.state[ru]
        dv = self.state[rv]
        if du > dv: ru, rv = rv, ru
        if du == dv: self.state[ru] -= 1
        self.state[rv] = ru
        
        
        return

def main():
    n=int(input())
    xx=[]
    yy=[]
    for i in range(n):
        x,y=MI()
        heappush(xx,[x,i])
        heappush(yy,[y,i])
    
    ee=[]
    px,pi=heappop(xx)
    while xx:
        x,i=heappop(xx)
        heappush(ee,[x-px,pi,i])
        pi,px=i,x
    py,pi=heappop(yy)
    while yy:
        y,i=heappop(yy)
        heappush(ee,[y-py,pi,i])
        pi,py=i,y
    
    uf=UnionFind(n)
    cnt=0
    ans=0
    while ee:
        d,u,v=heappop(ee)
        if uf.root(u)==uf.root(v):continue
        uf.merge(u,v)
        ans+=d
        cnt+=1
        if cnt==n-1:break
    print(ans)

main()

Solution (Python):
import sys
import numpy as np
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
read = sys.stdin.read

N, *xy = map(int, read().split())
xy = np.array(xy, np.int64).reshape(N, 2)
x = xy[:, 0]
y = xy[:, 1]

arg_x = np.argsort(x)
arg_x1 = arg_x[1:]
arg_x2 = arg_x[:-1]

arg_y = np.argsort(y)
arg_y1 = arg_y[1:]
arg_y2 = arg_y[:-1]

edges_x = x[arg_x1] - x[arg_x2]
edges_y = y[arg_y1] - y[arg_y2]

edges = np.concatenate([edges_x, edges_y])
towns_1 = np.concatenate([np.minimum(arg_x1, arg_x2), np.maximum(arg_y1, arg_y2)])
towns_2 = np.concatenate([np.maximum(arg_x1, arg_x2), np.minimum(arg_y1, arg_y2)])

graph = coo_matrix((edges, (towns_1, towns_2)), shape=(N, N)).tocsr()
tree = minimum_spanning_tree(graph, overwrite=True)
answer = int(tree.sum())

print(answer)

Solution (Python):
import sys
import numpy as np
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
read = sys.stdin.read

N, *xy = map(int, read().split())
xy = np.array(xy, np.int64).reshape(N, 2)
x = xy[:, 0]
y = xy[:, 1]

arg_x = np.argsort(x)
arg_x1 = arg_x[1:]
arg_x2 = arg_x[:-1]

arg_y = np.argsort(y)
arg_y1 = arg_y[1:]
arg_y2 = arg_y[:-1]

edges_x = x[arg_x1] - x[arg_x2]
edges_y = y[arg_y1] - y[arg_y2]

edges = np.concatenate([edges_x, edges_y])
towns_1 = np.concatenate([np.minimum(arg_x1, arg_x2), np.maximum(arg_y1, arg_y2)])
towns_2 = np.concatenate([np.maximum(arg_x1, arg_x2), np.minimum(arg_y1, arg_y2)])

graph = coo_matrix((edges, (towns_1, towns_2)), shape=(N, N))
tree = minimum_spanning_tree(graph, overwrite=True)
answer = int(tree.sum())

print(answer)

Solution (Python):
import sys
import numpy as np
read = sys.stdin.read


class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(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.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


N, *xy = map(int, read().split())
xy = np.array(xy, np.int64).reshape(N, 2)
x = xy[:, 0]
y = xy[:, 1]

arg_x = np.argsort(x)
arg_y = np.argsort(y)

edges_x = x[arg_x[1:]] - x[arg_x[:-1]]
edges_y = y[arg_y[1:]] - y[arg_y[:-1]]

edges = np.concatenate([edges_x, edges_y])
towns_1 = np.concatenate([arg_x[:-1], arg_y[:-1]])
towns_2 = np.concatenate([arg_x[1:], arg_y[1:]])

arg_edges = np.argsort(edges)
graph = zip(edges[arg_edges].tolist(), towns_1[arg_edges].tolist(), towns_2[arg_edges].tolist())

tree = UnionFind(N)
answer = 0

for d, t1, t2 in graph:
    if tree.isSameGroup(t1, t2):
        continue

    tree.Unite(t1, t2)
    answer += d

print(answer)

Solution (Python):
import sys
import numpy as np
read = sys.stdin.read


class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(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.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


N, *xy = map(int, read().split())
xy = np.array(xy, np.int64).reshape(N, 2)
x = xy[:, 0]
y = xy[:, 1]

arg_x = np.argsort(x)
arg_y = np.argsort(y)

edges_x = x[arg_x[1:]] - x[arg_x[:-1]]
edges_y = y[arg_y[1:]] - y[arg_y[:-1]]

edges = np.concatenate([edges_x, edges_y])
towns_1 = np.concatenate([arg_x[:-1], arg_y[:-1]])
towns_2 = np.concatenate([arg_x[1:], arg_y[1:]])

arg_edges = np.argsort(edges)
graph = zip(edges[arg_edges], towns_1[arg_edges], towns_2[arg_edges])

tree = UnionFind(N)
answer = 0

for d, t1, t2 in graph:
    if tree.isSameGroup(t1, t2):
        continue

    tree.Unite(t1, t2)
    answer += d

print(answer)

Solution (Python):
import sys
import numpy as np
read = sys.stdin.read


class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(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.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


N, *xy = map(int, read().split())
xy = np.array(xy, np.int64).reshape(N, 2)

town = np.arange(N)
arg_x = np.argsort(xy[:, 0])
arg_y = np.argsort(xy[:, 1])

edges_x = (xy[arg_x[1:], 0] - xy[arg_x[:-1], 0]).tolist()
town_x = town[arg_x].tolist()
town_x = zip(town_x[1:], town_x[:-1])

edges_y = (xy[arg_y[1:], 1] - xy[arg_y[:-1], 1]).tolist()
town_y = town[arg_y].tolist()
town_y = zip(town_y[1:], town_y[:-1])

edges = list(zip(edges_x, town_x)) + list(zip(edges_y, town_y))
edges.sort()

tree = UnionFind(N)
answer = 0

for d, (t1, t2) in edges:
    if tree.isSameGroup(t1, t2):
        continue

    tree.Unite(t1, t2)
    answer += d

print(answer)

Solution (Python):
import sys
import numpy as np
read = sys.stdin.read


class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(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.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


N, *xy = map(int, read().split())
xy = np.array(xy, np.int64).reshape(N, 2)

town = np.arange(N)
arg_x = np.argsort(xy[:, 0])
arg_y = np.argsort(xy[:, 1])

edges_x = xy[arg_x[1:], 0] - xy[arg_x[:-1], 0]
town_x = zip(town[arg_x[1:]], town[arg_x[:-1]])
edges_y = xy[arg_y[1:], 1] - xy[arg_y[:-1], 1]
town_y = zip(town[arg_y[1:]], town[arg_y[:-1]])

edges = list(zip(edges_x, town_x)) + list(zip(edges_y, town_y))
edges.sort()

tree = UnionFind(N)
answer = 0

for d, (t1, t2) in edges:
    if tree.isSameGroup(t1, t2):
        continue

    tree.Unite(t1, t2)
    answer += d

print(answer)